[코드트리] 술래잡기 (C++)

[문제]

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 해줄 때 괄호 빼먹어서 계속 틀렸다...조심하자