개발자 김수진

[풀이]

단순 구현 문제로 문제 조건만 잘 맞추고 문자열을 잘 다뤄주면 된다.

나는 우선 시간들을 convertTime 함수를 통해 int형으로 바꿔놓고 시작했다.

시간 string을 읽어와 분/초를 분리한뒤 {60*분 + 초}를 사용해 int형으로 계산했다.

이를 기반으로 commands의 작업들으 수행했는데 

1. check_opening을 통해 현재 시간이 opening 구간에 존재하는지 판단

2. prev, next 인지에 따라 시간 계산하도록 구현했다.

위의 과정을 반복하며 현재 시간을 계산한 뒤 

convertTimeToString 함수를 통해 현재 시간을 다시 mm:ss 타입의 String으로 변환하도록 하였다.

String.format 함수를 사용하여 문자열의 형식을 지정해줬다.

[코드]

class Solution {
    static int cur_pos;

    public String solution(String video_len, String pos, String op_start, String op_end, String[] commands) {
        int video_len_int = convertTime(video_len);
        int op_start_int = convertTime(op_start);
        int op_end_int = convertTime(op_end);
        cur_pos = convertTime(pos);
        
        for (String command : commands) {
            check_opening(op_start_int, op_end_int);
            if(command.equals("prev"))  move_prev();
            else move_next(video_len_int);
        }
        check_opening(op_start_int, op_end_int);
        return convertTimeToString();
    }
    
    public static void move_prev() {
        if(cur_pos - 10 <= 0)   cur_pos = 0;
        else    cur_pos -= 10;
    }
    
    public static void move_next(int end_time) {
        if(cur_pos + 10 >= end_time)   cur_pos = end_time;
        else    cur_pos += 10;
    }
    
    public static int convertTime(String time) {
        String[] parts = time.split(":");

        int min = Integer.parseInt(parts[0]); // 분
        int sec = Integer.parseInt(parts[1]); // 초
        return 60 * min + sec;
    }
    
    public void check_opening(int op_start, int op_end) {
        if(op_start <= cur_pos && op_end >= cur_pos){
            cur_pos = op_end;
        }
        return;
    }
    
	// mm:ss 형식의 문자열로 변환
    public static String convertTimeToString() {
        int minutes = cur_pos / 60;
        int seconds = cur_pos % 60;

        String formattedTime = String.format("%02d:%02d", minutes, seconds);
        return formattedTime;
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/340213

재귀 문제로 유명한 하노이의 탑

나무위키에 등록될 정도이다.

https://school.programmers.co.kr/learn/courses/30/lessons/12946?language=java

알고보니 굉장히 간단한 문제였다.

시작점을 a , 경유지를 b, 목적지를 c라고 하면

원판을 목적지까지 다 옮기기 위해서는 결국 



1. a  지점에서 제일 아래에 존재하는 가장 큰 원반을 제외한 원반들은 b 옮겨져야 한다.

2. 그리고 가장 큰 원반을 c로 옮기고

 3. b에 존재하는 원반들을 a 지점을 경유지로 두고 c로 옮겨야 한다.

1,2,3의 과정을 모두 수행하는 곳이 move 함수가 되는 것이다.

이걸 move 함수로 보면 a가 start, b가 tmp, c가 end가 된다.

import java.util.*;
class Solution {
    private static List<int[]> arr = new ArrayList<>();

    public int[][] solution(int n) {
        move(1,2,3,n);
        int[][] answer = arr.stream()
                .toArray(int[][]::new);

        return answer;
    }
    
    private static void move(int start, int tmp, int end, int cnt) {
         if(cnt == 0) {
             return;
         }
        move(start, end, tmp, cnt-1);
        arr.add(new int[]{start,end});
        move(tmp, start, end, cnt-1);
    }
}

[문제]

https://www.codetree.ai/problems/collect-coins/description

[풀이]

삼성전자 공채 모의 코딩테스트가 코드트리에 있길래 한번 풀어봤다. 굉장히 삼성스러운 문제..

NXN 격자에는  동전과  벽이 존재하며 주어진 시작점과 끝점 까지의 최단 거리를 구하면 된다.

시작점에서 끝점으로 가기 위해서는 최소 3개의 동전을 획득해야 하며 획득하는 동전의 순서는 동전의 번호가 작은 것부터 오름차순으로 획득할 수 있다.

또한 동전이 있는 곳을 지나가도 동전을 가져가지 않을 수 있으며 지나간 위치를 다시 지나갈 수 있다.

BFS와  DFS를 사용해 문제를 해결했다.

먼저 주어진 동전의 정보를 coin 이라는 벡터에 저장해두었다. 그리고 coin 벡터를 동전 번호를 기준으로 오름차순 정렬을 해주었다.

그리고 DFS를 통해 coin 벡터에 담긴 순서대로 동전을 선택하여 selectedCoin 벡터에 coin 벡터에서의 해당  동전의 index를 push했다.

DFS를 사용해 동전의 숫자가 오름차순으로 3개의 동전을 선택하여 최단거리를 구하였다.

최단거리를 구하는 방법으로는 BFS를 사용해 시작지점부터 종점부분까지의 거리를 구했다.

BFS는 최초 방문이 최단 경로가 되므로 queue에서 pop한 좌표가 종점인 경우 break 하도록 추가해줬다. (이거 안해주면 시간초과 발생)

최단거리 =  시작점부터 첫번째 동전까지의 거리 + 첫번째 동전 to 두번째 동전 거리 + 두번째 동전 to 세번째 동전 거리 + 세번째 동전 to 종점까지의 거리 

이 때 각 거리 계산 중 이동할 수 없는 좌표가 발생한다면 해당경로는 불가능한 경로이므로 -1을 return 하여 이동 불가능한 경로로 처리하였다.

[코드]

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define MAX 20

using namespace std;

struct pos{
    int x,y;
};

struct coinInfo{
    int idx,x,y;
};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int res=MAX*MAX;
int map[MAX][MAX]={0,};
int N;

pos startPos,endPos;

vector<coinInfo> coin;
vector<int> selected;

bool comp(coinInfo a, coinInfo b)
{
    if ( a.idx < b.idx) return true;
    return false;
}

int BFS(pos from, pos to)
{
    int visited[MAX][MAX]={0,};
    queue<pos> q;
    q.push(from);
    visited[from.x][from.y]=1;
    while(!q.empty()){
        int x= q.front().x;
        int y= q.front().y;
        q.pop();
        if(x==to.x && y == to.y)    break;
        for(int d=0;d<4;d++){
            int nx = x+dx[d];
            int ny = y+dy[d];
            
            if(nx<0||ny<0||nx>=N||ny>=N||map[nx][ny]==-1||visited[nx][ny] != 0)   continue;
            visited[nx][ny] = visited[x][y] + 1;
            q.push({nx,ny});
        }
    }
    
    return visited[to.x][to.y]-1;
}

int isPossible()
{
    int totalLen =0;
    int fromX,fromY;
    int toX, toY;
    
    for(int i=0;i<4;i++){
        if(i == 0){
            fromX = startPos.x; fromY = startPos.y;
            toX = coin[selected[i]].x;  toY = coin[selected[i]].y;
        } else if( i == 3){
            fromX = coin[selected[2]].x;    fromY = coin[selected[2]].y;
            toX = endPos.x;  toY = endPos.y;
        } else {
            fromX = coin[selected[i-1]].x;    fromY = coin[selected[i-1]].y;
            toX = coin[selected[i]].x;  toY = coin[selected[i]].y;
        }
        int len = BFS({fromX,fromY},{toX,toY});
        if( len == -1){
            totalLen = -1;
            break;
        }   else    totalLen += len;
    }
    
    return totalLen;
}

void selectCoin(int cnt, int idx)
{
    if( cnt == 3){
        int len = isPossible();
        if( len == -1)  return;
        if( len < res)  res = len;
        return ;
    }
    for(int i=idx;i<coin.size();i++){
        selected.push_back(i);
        selectCoin(cnt+1, i+1);
        selected.pop_back();
    }
}

void input()
{
    cin >> N;
    for(int i=0;i<N;i++){
        string str;
        cin >> str;
        for(int j=0;j<N;j++){
            
            if(str[j] == '#')   map[i][j]=-1;
            else if(str[j] == '.')  map[i][j]=0;
            else if(str[j] == 'S')  startPos={i,j};
            else if(str[j] == 'E')  endPos={i,j};
            else{
                map[i][j] = str[j] - '0';
                coin.push_back({map[i][j] , i, j});
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    input();
    // 코인 오름차순 정렬
    sort(coin.begin(), coin.end(), comp);
    selectCoin(0,0);
    if(res == MAX*MAX)    cout << "-1";
    else    cout << res;
    
    return 0;
}

[문제]

https://www.codetree.ai/frequent-problems/artistry/description

[풀이]

삼성전자 2022 상반기 오전 2번 문제.

N*N 격자에 대해 각 칸의 대한 색깔이 input으로 들어온다.

초기 예술 점수( 회전 안함) + 1회전 후 예술 점수 + 2회전 후 예술 점수 + 3회전 후 예술 점수를 출력해주면 된다.

1. 회전
2. 예술 점수 계산

각 step 별로 api를 구현하여 예술 점수를 계산하도록 했다.

초기에는 회전을 하지않고 예술 점수를 구하므로 calcScore api에서 예술 점수를 구하도록 했다.

calcScore에서는 BFS를 사용해 연속된 동일한 색깔끼리 그룹화를 하였다.

groupCnt를 통해 총 그룹의 개수를 저장

groupSize 배열에는 각 그룹에 대한 크기, groupIdx는 그룹에 해당하는 실제 색깔을 저장

또한 group 배열에는 grouping한 그룹의 index를 저장했다.

문제의 예시를 기준으로 보면 group 이차원 배열에는 다음과 같이 저장되어 있다.

그룹화를 마치면 calcTouch api에서 각 그룹별 맞닿는 변의 개수를 구하여 touch라는 이차원 배열에 저장해줬다.

각 칸 별로 아래 방향. 오른쪽 방향에 있는 칸을 확인하여 자신의 그룹과 다른 그룹이면 touch 배열의 [from][to]칸에 +1을 해주었다. 

각 칸 별로 아래, 오른쪽 방향에 대해서만  확인을 해주므로 두 개의 그룹이 맞닿는 변의 개수는 touch[from][to] + touch[to][from]이 된다.

이와 같이 맞닿는 변의 개수까지 구해주면 예술 점수를 구할 수 있다.

다음으로 rotate api를 통해 회전을 해주었다.

회전은 각 격자별 90도 시계 방향 회전이 있고 십자가 모양 부분을 90도 반시계 회전을 한다.

격자별 90도 시계 방향 회전을 인자가 다른 rotate api를 하나 더 선언하여 각 격자의 시작점을 인자 값으로 넘겨주었다.

[코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

#define MAX 30

using namespace std;

struct pos{
    int x,y;
};

int dx[4] ={ -1,0,1,0};
int dy[4] = {0,1,0,-1};

int N;
int map[MAX][MAX]={0,};
int group[MAX][MAX]={0,};
int touch[MAX*MAX][MAX*MAX]={0,};

void calcTouch()
{
    memset(touch, 0, sizeof(touch));

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int from = group[i][j];
            for(int k=1;k<=2;k++){
                int nx = i + dx[k];
                int ny = j + dy[k];
                
                if( nx <0 || ny <0 || nx >= N || ny >= N || group[nx][ny] == from)   continue;
                touch[from][group[nx][ny]]++;
            }
        }
    }
}

int calcScore()
{
    memset(group, 0, sizeof(group));

    int groupCnt=1;
    int groupSize[MAX*MAX]={0,};
    int groupIdx[MAX*MAX]={0,};
    queue<pos> q;

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if( group[i][j] == 0){
                q.push({i,j});
                group[i][j]=groupCnt;
                groupIdx[groupCnt] = map[i][j];
                groupCnt+=1;
            }
            while(!q.empty()){
                int x= q.front().x;
                int y= q.front().y;
                q.pop();
                
                groupSize[group[x][y]]++;

                for(int k=0;k<4;k++){
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    
                    if( nx <0 || ny <0 || nx >= N || ny >= N || group[nx][ny] != 0)   continue;
                    if( map[nx][ny] != map[x][y])   continue;
                    
                    q.push({nx,ny});
                    group[nx][ny]=group[x][y];
                }
            }
        }
    }
    
    calcTouch(); // 맞닿는 변 개수 계산
    int score=0;
    for(int i=1;i<groupCnt;i++){
        for(int j=i+1;j<=groupCnt;j++){
            score += (groupSize[i]+groupSize[j]) * (touch[i][j]+touch[j][i]) * groupIdx[i] * groupIdx[j];
        }
    }
    return score;
}

void rotate(int x,int y)
{
    int len = (N-1)/2;
    
    int tmp[MAX][MAX]={0,};
    
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            tmp[j][len-1-i] = map[x+i][y+j];
        }
    }
    
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            map[x+i][y+j]=tmp[i][j];
        }
    }
    
}
void rotate()
{
    int len = (N-1)/2 + 1;
    
    rotate(0,0);
    rotate(0,len);
    rotate(len,0);
    rotate(len,len);

    int tmp[MAX]={0,};
    len-=1;
    
    for(int i=0;i<len;i++)  tmp[i] = map[i][len];
    for(int i=0;i<len;i++)  map[i][len] = map[len][N-1-i];
    for(int i=0;i<len;i++)  map[len][N-1-i]= map[N-1-i][len];
    for(int i=0;i<len;i++)  map[N-1-i][len]=map[len][i];
    for(int i=0;i<len;i++)  map[len][i]=tmp[i];

}

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)    cin >> map[i][j];
    }
    int score =0;
    
    score += calcScore();
    
    for(int i=0;i<3;i++){
        rotate();
        score += calcScore();
    }
    cout << score;
    return 0;
}

[문제]

https://www.codetree.ai/frequent-problems/tree-kill-all/description

[풀이]

삼성전자 22년 상반기 SW 역량테스트 오후 2번 문제

1. 인접한 4개의 칸에 나무의 개수만큼 성장

2. 인접한 4개의 칸에 벽.다른 나무.제초제가 없는 칸에 대해 번식 진행

3. 나무가 가장 많이 박멸되는 곳에 제초제 뿌림

   - 벽 또는 나무가 없는 칸의 경우 그 이후 칸에는 제초제를 전파하지 못함

   - 이러한 칸이 여러개면 행이 작은 칸에 , 행이 같으면 열이 더 작은 칸에 제초제를 뿌린다.

각 스텝별로 api를 만들었다.

먼저 1번의 경우  growthTree에서 처리해줬다. 현재 나무가 존재하는 칸에 대해 인접한 칸의 나무가 존재하는 칸의 개수만큼 성장하도록 구현

2번의 경우 breedTree에서 조건문을 통해 제초제. 다른 나무. 벽의 존재 여부를 확인 후 없다면 번식을 진행하도록 구현해줬다.

그 다음으로 제초제는 매년 1씩 감소하므로 deleteHerb에서 제초제가 존재하는 칸에 대해 -1씩 해주었다.

마지막으로  dieTree에서 3번을 처리해주었다. 제초제를 뿌릴 수 있는 모든 칸에 대해 확인해주었다.

각 칸 마다 박멸하는 나무의 개수.행.열을 벡터에 저장하여 comp 함수를 통해 정렬을 해주었다.

또한 map에서는 나무가 없는 빈 칸과 제초제가 뿌려진 곳을 모두 0으로 처리하여 따로 구분해주지 않았다.

제초제가 뿌려진 곳은 herb 배열의 0이 아닌 칸이 되므로 빈칸과 제초제가 뿌려진 칸을 비교할 수 있다.

[코드]

//m년 동안 총 박멸한 나무의 그루 수를 구하는 프로그램을 작성해보세요

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 20

using namespace std;

struct info{
    int cnt,x,y;
};

int dx[8] = {0,-1,-1,-1,0,1,1,1};
int dy[8] = {-1,-1,0,1,1,1,0,-1};

int N,M,K,C;
int map[MAX][MAX]={0,};
int herbicide[MAX][MAX]={0,};
int res =0;

bool comp( info a, info b)
{
    if(a.cnt > b.cnt )  return true;
    else if(a.cnt < b.cnt )  return false;

    if(a.x < b.x )  return true;
    else if(a.x > b.x )  return false;

    if(a.y < b.y )  return true;
    return false;
}

void growthTree()
{
    int addTree[MAX][MAX]={0,};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j] <= 0)  continue;
            int cnt =0;
            for(int k=0;k<8;k+=2){
                int nx = i + dx[k];
                int ny = j + dy[k];

                if( nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if( map[nx][ny] <= 0)   continue;
                cnt++;
            }
            addTree[i][j]=cnt;
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            map[i][j] += addTree[i][j];
        }
    }
}

void breedTree()
{
    int addTree[MAX][MAX]={0,};

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j] <= 0)  continue;
            int cnt =0;
            for(int k=0;k<8;k+=2){
                int nx = i + dx[k];
                int ny = j + dy[k];

                if( nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] != 0 || herbicide[nx][ny] != 0) continue;
                
                cnt++;
            }
            for(int k=0;k<8;k+=2){
                int nx = i + dx[k];
                int ny = j + dy[k];

                if( nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] != 0 || herbicide[nx][ny] != 0) continue;
                addTree[nx][ny]+=map[i][j]/cnt;
            }
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            map[i][j] += addTree[i][j];
        }
    }
}

void dieTree()
{
    vector<info> die;

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if( map[i][j] <= 0)  continue;
            int cnt = map[i][j];
            for(int d=1;d<8;d+=2){
                for(int l=1;l<=K;l++){
                    int nx = i + dx[d]*l;
                    int ny = j + dy[d]*l;
                    if( nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] <= 0) break;
                    cnt += map[nx][ny];
                }
            }
            if(cnt > 0)   die.push_back({cnt,i,j});
        }
    }
    

    
    if( die.size() == 0)    return ;
    sort(die.begin(), die.end(),comp);
    res += die[0].cnt;
    int x =die[0].x;
    int y =die[0].y;
    
    if( map[x][y] > 0){
        map[x][y] = 0;
        herbicide[x][y] = C;

        for(int d=1;d<8;d+=2){
            for(int l=1;l<=K;l++){
                int nx = x + dx[d]*l;
                int ny = y + dy[d]*l;
                if( nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] <0 ) break;
                
                herbicide[nx][ny] = C;
                
                if( map[nx][ny] == 0 ){
                    break;
                } else {
                    map[nx][ny] = 0;
                }
            }
        }
    }
    
}

void deleteHerb()
{
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(herbicide[i][j] == 0)    continue;
            herbicide[i][j]-=1;
        }
    }
}

int main(void)
{
    cin >> N >> M >> K >> C;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)    cin >> map[i][j];
    }

    for(int i=0;i<M;i++){
        growthTree();
        breedTree();
        deleteHerb();
        dieTree();
    }
    cout << res;
    return 0;
}

[문제]

https://www.acmicpc.net/problem/20056

[풀이]

N*N 격자에 파이어볼 M개가 존재한다.

각 파이어볼은 질량(m), 속력(s), 방향(d)을 가지고 있다.

1. 모든 파이어볼이 d 방향으로 s만큼 움직인다,.

2. 2개 이상의 파이어볼이 있는 칸은 하나의 파이어볼로 합쳐진다.

 - 합쳐진 파이어볼은 4개의 파이어볼로 나뉘어진다.

- 각 파이어볼의 질량은 ( 합쳐진 파이어볼의 질량 합 / 5 )

- 각 파이어볼의 속력은 ( 합쳐진 파이어볼의 속력 합 / 파이어볼의 개수) 

- 모든 파이어볼의 방향이 홀수 또는 짝수로 일치할 경우 나뉘어진 파이어볼의 방향은 0,2,4,6이 되고 아닌 경우 1,3,5,7이 된다.

1번과 2번에 대해 각각의 api로 관리했다. 파이어볼이 이동하는 것은 moveBall에서 처리하고 파이어볼이 나뉘어 지는 것은 divideBall api에서 처리해주었다.

첫번째로 moveBall에서 파이어볼을 이동시켰다.

문제에서 주어진 조건으로 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 

따라서 (1,1)을 기준으로 시작하여 s%N 만큼 이동하도록 해주었다. 또한 이동한 위치가 1보다 작거나 N보다 클 경우 N만큼 빼주거나 더해주어 이동위치를 계산했다.

그리고 두번째로 이동한 파이어볼에 대해 문제 조건에 맞게 divideBall에서 파이어볼을 나눠주도록 처리했다.

[코드]

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 51

using namespace std;

struct Ball{
    int m,s,d;
};
int N,M,K;
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

vector<Ball> fireBall[MAX][MAX];

void moveBall()
{
    vector<Ball> tmpBall[MAX][MAX];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int k=0;k<fireBall[i][j].size();k++){
                int s= fireBall[i][j][k].s%N;
                int d= fireBall[i][j][k].d;
                
                int nx = i+dx[d]*s;
                int ny = j+dy[d]*s;
                
                
                if(nx < 1)   nx+=N;
                if(nx > N) nx -=N;
                
                if(ny < 1)   ny+=N;
                if(ny > N) ny-= N;
                
                tmpBall[nx][ny].push_back(fireBall[i][j][k]);
            }
        }
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            fireBall[i][j].clear();
            fireBall[i][j] = tmpBall[i][j];
        }
    }
}

void divideBall()
{
    vector<Ball> tmpBall[MAX][MAX];

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if ( fireBall[i][j].size() == 1){
                tmpBall[i][j] = fireBall[i][j];
            }
            else if ( fireBall[i][j].size() >= 2){
                int totalS=0;
                int totalM=0;
                bool even=false;
                bool odd=false;
                
                for(int k=0;k<fireBall[i][j].size();k++){
                    int dir=fireBall[i][j][k].d;
                    if(dir % 2 == 0)    even = true;
                    else    odd = true;
                    
                    totalS+=fireBall[i][j][k].s;
                    totalM+=fireBall[i][j][k].m;
                }
                
                int m = totalM/5;
                int s = totalS/fireBall[i][j].size();
                int dir = even && odd ? 1 : 0;
                 if ( m > 0)
                 {
                     for(int d=dir;d<8;d+=2){
                        tmpBall[i][j].push_back({m,s,d});
                    }
                 }
            }
            fireBall[i][j].clear();
            fireBall[i][j] = tmpBall[i][j];
        }
    }
    
}

int main(void)
{
    ios::sync_with_stdio(false);
    
    cin >> N >> M >> K;
    
    for(int i=0;i<M;i++){
        int x,y,m,s,d;
        cin >> x >> y >> m >> s >> d;
        fireBall[x][y].push_back({m,s,d});
    }
    for(int i=0;i<K;i++){
        moveBall();
        divideBall();
    }
    
    long long totalM =0;
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int k=0;k<fireBall[i][j].size();k++)    totalM+=fireBall[i][j][k].m;
        }
    }
    
    cout << totalM;
    return 0;
}

[문제]

https://www.acmicpc.net/problem/20058

[풀이]

파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다.

격자별 회전을 처리해주기 위해 rotate api의 인자로 각 격자의 시작 점과 길이를 넘겨주도록 했다.

(0,0)을 기준으로 90도 시계 방향 회전하면 (x,y) -> (y, (N-1)-x)로 위치가 변한다.

그런데 해당 문제에서는 격자별로 90도 회전이므로 0부터 len 이전까지 반복하면서 tmp 배열에 (0,0)부터 회전한 값을 저장한다.

tmp[j][len-1-i] = map[x+i][y+j];

그리고 tmp (0,0)부터 (len-1,len-1) 까지 다시 map 배열로 옮겨준다.

map[x+i][y+i] = tmp[i][j];

이와 같은 방식으로 90도 회전을 구현했다.

회전 후 melt_ice api를 통해 얼음을 녹여준다.

그리고 find_max_lump api에서 남아있는 얼음의 합을 구하고 가장 큰 덩어리가 차지하는 칸의 개수를 출력해줬다. 

[코드]

#include <iostream>
#include <queue>

#define MAX 70

using namespace std;

struct pos {
    int x,y;
};

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int N,Q,L;
int map[MAX][MAX]={0,};

// 격자 시계방향 회전
void rotate(int x, int y, int len){
    int tmp[MAX][MAX]={0,};

    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            tmp[j][len-1-i]=map[x+i][y+j];
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            map[x+i][y+j]=tmp[i][j];
}

void rotate_grid()
{
    int len = 1 << L;
    
    for(int i=0;i<N;i+=len){
        for(int j=0;j<N;j+=len){
            rotate(i,j,len);
        }
    }
}

void melt_ice()
{
    int tmp[MAX][MAX]={0,};
    
    for(int x=0;x<N;x++){
        for(int y=0;y<N;y++){
            int cnt =0;
            for(int k=0;k<4;k++){
                int nx = x+dx[k];
                int ny = y+dy[k];
                if( nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if( map[nx][ny] != 0 )  cnt++;
            }
            if (cnt < 3) {
                if( map[x][y] != 0) tmp[x][y] = map[x][y] -1;
            }
            else tmp[x][y] = map[x][y];
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            map[i][j] = tmp[i][j];
        }
    }

}

int find_max_lump()
{
    bool visited[MAX][MAX]={0,};
    int res =0;
    queue<pos> q;
    int sum=0;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int cnt =0;
            sum += map[i][j];
            if(map[i][j] <= 0 || visited[i][j] )
                continue;
        
            q.push({i,j});
            visited[i][j]=1;
            
            while(!q.empty()){
                cnt++;
                int x= q.front().x;
                int y= q.front().y;
                q.pop();
                
                for(int k=0;k<4;k++){
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    
                    if( nx < 0 || ny <0 || nx >= N || ny >=N || visited[nx][ny] || map[nx][ny] <= 0)    continue;
                    visited[nx][ny] = 1;
                    q.push({nx,ny});
                }
            }
            if( res < cnt)  res = cnt;
        }
    }
    cout << sum << "\n";
    return res;
}

int main(void)
{
    std::ios::sync_with_stdio(false);

    cin >> N >> Q;
    N = 1 << N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)    cin >> map[i][j];
    }
    for(int i=0;i<Q;i++){
        cin >> L;
        rotate_grid();
        melt_ice();
    }
    cout << find_max_lump();
    return 0;
}

[문제]

https://www.codetree.ai/frequent-problems/hide-and-seek/description

[풀이]

삼성 22 상반기 SW 역량 오전 1번 문제로 달팽이 회전에 잘 처리해준다면 문제 없이 해결할 수 있는 문제인 것 같다.

1. m명의 도망자가 움직인다.
   
   1. 이 때 술래와 거리가 <=3인 도망자만 움직인다.
   2. 움직이려는 칸에 술래가 있으면 움직이지 않고 나무가 있는 경우는 움직여도 된다.
   3. 움직이려는 위치가 격자를 벗어난다면 방향을 틀고 움직인다. 이 때도 마찬가지로 술래가 있다면 방향만 틀고 움직이지 않는다.
2. 술래가 한칸 움직인다. 
   1. 술래는 달팽이 방향으로 움직이고 이동 후 위치가 방향 트는 부분이면 바로 튼다.
3. 술래가 도망자를 잡는다.
   1. 현재 술래의 방향을 기준으로 현재 칸(술래가 존재하는 칸) 포함 3칸에 존재하는 도망자를 잡을 수 있다.
   2. 해당 칸에 나무가 존재한다면 도망자를 잡지 못한다.
   3. 이 때 도망자를 잡으면 점수를 얻게 되는데 t 번째 턴에 잡은 도망자 수를 곱하여 ( t * 도망자 수) 가 점수가 된다.

이런식으로 반복하여 도망자를 잡아 얻은 점수를 출력하면 된다.

위의 과정을 각각 api로 나눠서 구현했다.

도망자가 움직이는 과정은 moveRunner. 술래가 움직이는건 moveSullae, 도망자가 잡히는건 catchRunner 

첫번째로 moveRunner에서 술래와 거리가 3 이하인 도망자만 움직이도록 구현했다.

도망자 정보는 이차원 배열 벡터를 사용해 관리하고 도망자가 움직인 정보를 tmpRuunerMap이라는 변수에 담아뒀다가 모든 도망자가 이동하면 기존 runnerMap을 초기화 하고 tmpRunnerMap의 정보를 runnerMap으로 옮겨줬다.

두번째로 moveSullae api에서 술래가 움직인다. 술래는 달팽이 방향으로 1번의 턴에 한칸씩 움직인다. 달팽이 방향 회전은 1,1,2,2,3,3,4,4, 이런식으로 같은 길이가 두번씩 반복하고 길이가 1 추가된다. 따라서 전역 변수로 len과 cnt를 선언해주어 해당 길이를 몇 번 돌았는지 체크해준다. 이 때 cnt가 2가 되면 len을 1 추가해주었다. 또한 len 만큼 다 돌면 방향을 틀게끔 sullae의 dir을 업데이트 해주었다. 또한 술래가 정방향으로 한바퀴 다 돌고나면 다시 역방향으로 돌아야 하므로 opposite라는 전역변수를 추가해주어 역방향인지 정방향인지 구분해주었다. 또한 len 만큼 다 돌아서 술래가 방향을 틀어야하는 위치인 경우에 방향도 바로 업데이트 해주었다.

마지막으로 catchRunner에서 현재 술래의 위치를 기준으로 술래 방향으로 3칸 이내에 존재하는 도망자를 잡도록 해주었다.

[코드]

#include <iostream>
#include <vector>
#define MAX 100
using namespace std;

struct Info{
    int x,y,dir;
};

Info sullae;

bool namu[MAX][MAX]={0,};
vector<int> runnerMap[MAX][MAX];
// int map[MAX][MAX]={0,};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int N,M,H,K;
bool opposite= false;
int len, cnt;
//목표 len
int curLen= 1;
void moveRunner()
{
    vector<int> tmpRunnerMap[MAX][MAX];

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<runnerMap[i][j].size();k++){
                
                int d= runnerMap[i][j][k];
                int dis = abs(i-sullae.x) + abs(j-sullae.y);
                if(dis > 3) {
                    tmpRunnerMap[i][j].push_back(runnerMap[i][j][k]);
                    continue;
                }

                int nx = i+dx[d];
                int ny = j+dy[d];

                if( nx < 0 || ny < 0 || nx >= N || ny >= N) {
                    if( d < 2)  d += 2;
                    else    d -= 2;

                    nx = i + dx[d];
                    ny = j + dy[d];
                }

                if ( nx == sullae.x && ny == sullae.y)  {
                    nx = nx - dx[d];
                    ny = ny - dy[d];
                }

                tmpRunnerMap[nx][ny].push_back(d);
            }
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            runnerMap[i][j].clear();
            runnerMap[i][j] = tmpRunnerMap[i][j];
        }
    }

}

int catchRunner()
{
    int x = sullae.x;
    int y = sullae.y;
    int dir = sullae.dir;

    int cnt =0;
    for(int i=0;i<3;i++)
    {
        int nx = x+dx[dir]*i;
        int ny = y+dy[dir]*i;
        if( namu[nx][ny])   continue;
        if( nx <0 || ny <0 || nx >= N || ny >= N)   break;

        if( runnerMap[nx][ny].size() > 0){
            cnt += runnerMap[nx][ny].size();
            runnerMap[nx][ny].clear();
        }
    }
    return cnt;
}

void moveSullae()
{
    int x =sullae.x;
    int y =sullae.y;
    int dir = sullae.dir;

    int nx = x+dx[dir];
    int ny = y+dy[dir];

    len++;

    if ( len == curLen ) {
        len=0;
        cnt++;
        if( opposite == false){
            if(dir == 3)    dir = 0;
            else    dir++;
        }
        else {
            if ( dir == 0 ) dir = 3;
            else    dir--;
        }
        if (cnt == 2)  {
            cnt = 0;
            if(!opposite)    curLen++;
            else    curLen--;

        }
    }

    if(nx == 0 && ny == 0){
        opposite= true;
        curLen = N-1;
        dir = 2;
        cnt = -1;
        len = 0;
    } else if(nx == (N-1)/2 && ny == (N-1)/2) {
        opposite= false;
        curLen=1;
        dir = 0;
        cnt = 0;
        len = 0;
    }
    sullae = {nx,ny,dir};
}

int main(void)
{
    ios::sync_with_stdio(false);

    curLen = 1;
    len = 0;
    cnt = 0;

    cin >> N >> M >> H >> K;
    sullae = { (N-1)/2, (N-1)/2,0};
    
    for(int i=0;i<M;i++){
        int x,y,d;
        cin >> x >> y >> d;
        if( d==1)   d = 1;
        else    d = 2;
        runnerMap[x-1][y-1].push_back(d);
    }
    
    for(int i=0;i<H;i++){
        int x,y;
        cin >> x >> y;
        namu[x-1][y-1] = 1;
    }

    int score =0;
    
    for(int i=1;i<=K;i++){
       moveRunner();
        moveSullae();
       score += i * catchRunner();
    }
    cout << score;
    return 0;
}

그리고 (N-1)/2 해줄 때 괄호 빼먹어서 계속 틀렸다...조심하자