[Algorithm] 백준 13787 Infinity Maze

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

백준에서 문제 찾아보다가 이름이 맘에 드는 문제를 발견했습니다. 재작년에 출시한 게임 iMaze와 같은 이름! 너무 반가워서 바로 풀어보았습니다.

문제가 영어로 되어있어서 우리말로 풀어볼게요.

문제

후쿠오카 박사는 2D 미로에 간단한 로봇을 배치시켰습니다. 미로는 출구가 없어서 로봇이 밖으로 나갈 수 없습니다. 아래 그림처럼 H x W 격자 셀로 만들어졌고, 미로의 위, 오른쪽, 아래, 왼쪽은 각각 북(N), 동(E), 남(S), 서(W)쪽입니다.

각 셀은 벽(#)이거나 빈 공간(.)이고, 좌표 (i, j)에 대해 i는 남쪽으로 갈수록 커지고, j는 동쪽으로 갈수록 커져서, 가장 왼쪽 위부터 (1, 1), 가장 오른쪽 아래는 (H, W)입니다.

로봇은 네가지 방향으로 움직이며, 진행 방향에 있는 셀이 빈 공간인 경우 이동하고, 벽이 있을 경우엔 오른쪽으로 90도 회전합니다. 이러한 규칙으로 총 L번 이동한 후 멈춥니다.

미로의 모습, 로봇의 초기 위치와 방향, 그리고 이동 횟수(L)가 주어졌을 때, 로봇이 마지막에 멈춘 위치와 그 때 로봇이 향하고 있는 방향을 구하는 프로그램을 구하세요.

 

입력

다음과 같은 형태로 여러 번 주어집니다.

H W L
c1,1 c1,2 . . . c1,W
. 
. 
. 
cH,1 cH,2 . . . cH,W

H, W는 미로의 크기, L은 이동 횟수입니다. (1 ≤ H, W ≤ 100, 1 ≤ L ≤ 10^18)

각 H 개의 줄에는 W 개의 문자가 입력으로 들어옵니다. i번째 줄 j번째 문자는 위 형태에서 ci,j, 즉 좌표 (i, j)를 뜻합니다. ci,j 에 '.' 이 있으면 그 좌표는 빈 공간이고, '#'이 있으면 그 좌표엔 벽이 있습니다. 그리고 'N', 'E', 'S', 'W'가 있으면 그 위치가 로봇의 초기 위치이며, 로봇이 맨 처음에 북, 동, 남, 서 중 어느 쪽을 바라보고 있는지 나타냅니다.

초기에 주어진 로봇의 옆에는 적어도 하나 이상의 빈 공간이 존재합니다.

H W L에 0 0 0 이 들어가는 경우 프로그램을 종료합니다.

 

출력

각 데이터셋에 대해서 마지막 줄에 로봇의 마지막 위치 i, j 와 그 때의 방향  'N', 'E', 'S', 'W' 중 하나로 하여, 공백(' ')을 사이에 두고 출력합니다.

출력 예제는 백준에서~

 

풀이

0. 변수 선언
먼저 L이 10^18까지 들어올 수 있기 때문에 long long으로 선언해줘야 합니다. 저는 L 대신 moves라고 선언했습니다. 저는 xy 좌표계가 익숙하기 때문에 H, W는 각각 Y, X로 표현했고, 문제에서의 i는 y, j는 x에 대응되며, 문제에서와 달리 코드에서 좌표는 0부터 시작합니다. (그래서 마지막에 출력할때만 1씩 더해줍니다.)

1. N, E, S, W를 0, 1, 2, 3에 대응하여 순회
이렇게 대응시켜주면 방향을 의미하는 변수 d에 대해서 (d + 1) % 4 만 해주면, 오른쪽으로 돌았다고 볼 수 있습니다. 벽을 만났을 때, for문(i=0;i<3;++i)에서 (d+i)%4 로 방향을 설정한 후에 진행 좌표가 빈 공간인 경우 for문을 break하고 해당 좌표로 이동, moves를 1 감소시켜줍니다.

2. 반복되는 구간
미로를 돌다 보면 출구가 없기 때문에 이동 횟수가 너무 많다면 반복되는 구간이 있을 것입니다. 이를 고려하지 않고 L번 전부 이동한다면 시간 초과가 뜹니다. 그 반복되는 구간이 어딘지 처음에는 알 수 없기 때문에 일단 돌아주는데, 그래서 visited[Y][X][4] 배열을 선언해줍니다. 어떤 좌표에 어떠한 방향을 향해 몇 번 도달했는지를 저장합니다. 초기값은 0부터, 로봇이 어느 좌표에 도달할 때마다 바로 visited[y][x][d]++ 해줍니다.

visited[y][x][d]의 값이 1 인 경우라면, 방금 여기에, 이 방향으로 도달했다는 뜻이고, 2인 경우에는 이 좌표에 같은 방향 d로 2번째로 도달했다는 얘기입니다. 같은 위치에 같은 방향으로 도달했다면 이 다음은 반드시 반복된다는 뜻이죠. 이 정보(Point)를 loops 라는 이름의 vector에 추가해줍니다. 그리고 visited[y][x][d] 값이 3이 되었을 때는 이 위치에 세번째 도달했다는 뜻이고, 두번째 도달했을때부터 세번째 도달할 때까지 지나간 자취가 앞으로 계속 반복될 것입니다. 그래서 앞서 loops 에 이 자취를 저장한 것입니다.

3. 반복되는 이동 제거
visited[y][x][d] 값이 3이 되면 해당 while문(moves > 0)을 break합니다. 이 때 moves를 loops의 크기로 나누면 반복되는 이동을 생략할 수 있고, 그 몫의 나머지만큼만 더 이동해주면 되겠죠. 나머지만큼 더 이동하면 loops[나머지]가 나오고, 그 정보를 출력하면 답이 됩니다.

#include <iostream>
#include <vector>
using namespace std;

#define FOR(i, e) for(int i=0 ; i<e ; ++i)

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

int getDirection(char c)
{
    return  c == 'N' ? 0 :
            c == 'E' ? 1 :
            c == 'S' ? 2 :
            c == 'W' ? 3 : -1;
}

char directions[4] = {'N', 'E', 'S', 'W'};

struct Point
{
    int x, y, d;
};

int main()
{
    int Y = 1, X = 1;
    long long moves = 1;

    while(Y > 0 && X > 0)
    {
        cin >> Y >> X >> moves;

        char map[Y][X];
        short visited[Y][X][4];
        FOR(y, Y) FOR(x, X) FOR(i, 4) visited[y][x][i] = 0;

        int nowX = 0, nowY = 0, nowD = 0; // nowD : 0, 1, 2, 3 : N, E, S, W
        
        FOR(y, Y) FOR(x, X)
        {
            cin >> map[y][x];

            int d = getDirection(map[y][x]);
            if(d >= 0)
            {
                nowX = x; nowY = y; nowD = d;
            }
        }

        vector<Point> loops;
        while(moves > 0)
        {
            visited[nowY][nowX][nowD]++;
            if(visited[nowY][nowX][nowD] == 2)
            {
                loops.push_back({nowX, nowY, nowD});
            }
            else if(visited[nowY][nowX][nowD] == 3)
            {
                moves %= loops.size();
                nowY = loops[moves].y;
                nowX = loops[moves].x;
                nowD = loops[moves].d;
                break;
            }

            for(int i=0 ; i<3 ; ++i)
            {
                int nextD = (i + nowD) % 4;
                int nextX = nowX + dx[nextD];
                int nextY = nowY + dy[nextD];

                if(nextX >= 0 && nextY >= 0 && nextX < X && nextY < Y && map[nextY][nextX] != '#') break;

                nowD = nextD;
            }

            nowX += dx[nowD];
            nowY += dy[nowD];

            moves--;
        }

        if(Y > 0 && X > 0) cout << nowY + 1 << ' ' << nowX + 1 << ' ' << directions[nowD] << '\n';
        else break;
    }
    
    return 0;
}