2024 삼성SW역량테스트 하반기 오전 1번

https://www.codetree.ai/training-field/frequent-problems/problems/escape-unknown-space/description?page=1&pageSize=10

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

위 문제의 핵심 구현사항은 아래와 같습니다.

 

1. 3차원 정육면체의 최단거리를 어떻게 구현할 수 있을까?

 

1번에 잘못된 접근 (처음 나의 생각)

 

정육면체를 평면도로 펼쳐서 BFS로 최단거리를 구하면 되지 않을까?

 

윗면에서 다른면으로 이동하는 최단경로는 구할 수 있습니다

 

하지만

 

아랫면에서 다른 면으로 이동하는 경우는 구현할 수 없습니다.

 

이를 그림으로 표현하면 아래와 같습니다.

 

위 그림처럼 윗면에서 다른면으로 이동하는 최단경로 BFS로 구현할 수 있지만

 

파란색 화살표 처럼 윗면이 아닌 평면에서 다른 윗면이 아닌 평면으로 이동하는 경우를 BFS로 구현하지 못 했습니다.

---

1번에 대한 올바른 접근

 

각 평면( 시간의 방 평면 5개 + 미지의 공간 평면 1개 )의 좌표에 대해 번호를 할당하고 할당된 번호를 활용하여 인접 행렬을 구현한다면 이를 해결할 수 있습니다.

 

인접 행렬은 각 좌표에서 동 남 북 서 방향으로 인접한 좌표 번호를 할당합니다.

 

 

이렇게 각 좌표에 대해 번호를 할당하고 동 남 북 서 방향으로 인접한 번호를 통해 인접행렬 그래프를 만들 수 있습니다.

 

예를들어

 

 

위 그림에서 1번은 2 3 4 5 번의 좌표로 이동할 수 있습니다.

 

이를 2차원 인접행렬로 표현하면 아래와 같습니다.

 

 

이제 위 내용을 코드로 구현하면 아래와 같습니다.

 

우선 각 좌표를 순회하며 번호를 할당합니다.

cnt 변수를 증가시키며 번호를 할당합니다.

↓

static void build_graph(int N, int M) {
        int cnt = 0;

        // 각 셀에 대해 대응될 번호를 차례로 부여합니다
        // 평면도 중 시간의 벽이 아닌 부분의 셀들을 순회한 후,
        // 단면도에 속하는 셀들을 단면도의 동쪽 -> 남쪽 -> 서쪽 -> 북쪽 -> 위쪽 순으로 셀들을 순회하면서 번호를 부여합니다
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(spaceMap[i][j] != 3) { // 시간의 벽이 있는 셀이 아닌 경우에만 번호를 부여합니다
                    spaceMapCellId[i][j] = ++cnt;
                }
            }
        }

        // 단면도의 동쪽, 남쪽, 서쪽, 북쪽, 위쪽 순으로 순회하며 셀에 번호를 부여합니다
        for(int t = 0; t < 5; t++) {
            for(int i = 0; i < M; i++) {
                for(int j = 0; j < M; j++) {
                    timeWallCellId[t][i][j] = ++cnt;
                }
            }
        }
        
        ...

 

 

이후 graph 인접행렬을 생성하고 이동할 수 있는 좌표끼리 연결해줍니다.

graph 인접행렬을 (cnt + 1) x (4) 크기로 생성합니다. 

이후  미지의 공간을 순회하며 인접행렬에 값을 입력합니다.

cnt + 1 로 행 크기를 지정한 이유는 각 좌표에 대한 번호를 1번 부터 할당했기 때문입니다. 

↓

	graph = new int[cnt+1][4];
        for(int i = 0; i < cnt+1; i++) {
            Arrays.fill(graph[i], -1);
        }

        // 간선을 추가하는 작업을 위해 사용할 dx, dy 배열
        // 동, 남, 북, 서에 대응되는 순서로 채워져 있습니다
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        // 평면도에 속하는 셀에 대응되는 번호의 정점 쌍에 대해 간선을 추가합니다
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(spaceMap[i][j] != 3) { // 현재 셀에 장애물이 없는 경우

                    int idx = spaceMapCellId[i][j];

                    // 동, 남, 북, 서 순으로 인접한 셀들을 탐색합니다
                    for(int dd = 0; dd < 4; dd++) {
                        int nx = i + dx[dd];
                        int ny = j + dy[dd];

                        // 범위를 벗어나면 넘어갑니다
                        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                        // 셀에 장애물이 있는 경우 넘어갑니다
                        if(spaceMap[nx][ny] == 3) continue;

                        // 그렇지 않은 경우, 이어줍니다
                        graph[idx][dd] = spaceMapCellId[nx][ny];
                    }
                }
            }
        }

 

시간의 방 동 남 서 북  평면도 간 (윗면 제외) 인접행렬을 생성합니다.

 

이때 5 x M x M   크기 3차원 배열 timeWallCellId을

timeWallCellId[0][ ][ ] : 동쪽 평면도

timeWallCellId[1][ ][ ] : 남쪽 평면도

timeWallCellId[2][ ][ ] : 서쪽 평면도

timeWallCellId[3][ ][ ] : 북쪽 평면도

timeWallCellId[4][ ][ ] : 위쪽 평면도

(동 서 남 북) 순서가 아닌 (동 남 서 북) 순서로초기화 했기 때문에 + 연산자와 % 연산자로 평면도를 순회하며 인접한 경우를 구현할 수 있습니다.

문제에서는 (동 서 남 북) 평면도 순서대로 입력이 주어집니다.

↓

// 단면도의 동쪽, 남쪽, 서쪽, 북쪽에 있는 셀들이 인접할 경우
        // 대응되는 번호의 정점들을 이어줍니다
        for(int t = 0; t < 4; t++) {
            for(int i = 0; i < M; i++) {
                for(int j = 0; j < M; j++) {

                    int idx = timeWallCellId[t][i][j];

                    // 위와 비슷하게 4방향 탐색
                    for(int dd = 0; dd < 4; dd++) {
                        int nx = i + dx[dd];
                        int ny = j + dy[dd];

                        // 행 범위가 넘어갔을 경우 통과
                        if(nx < 0 || nx >= M) continue;

                        // 열 번호가 0보다 작아질 경우, 시계방향순으로 하나 앞에 있는 단면도의 가장 오른쪽 열의 셀과 인접합니다
                        if(ny < 0) {
                            graph[idx][dd] = timeWallCellId[(t+1)%4][nx][M-1];
                        }
                        // 열 번호가 M-1보다 커질 경우, 반시계방향순으로 하나 앞에 있는 단면도의 가장 왼쪽 열의 셀과 인접합니다
                        else if(ny >= M) {
                            graph[idx][dd] = timeWallCellId[(t+3)%4][nx][0];
                        }
                        // 그 외의 경우 평면도의 경우처럼 이어줍니다
                        else {
                            graph[idx][dd] = timeWallCellId[t][nx][ny];
                        }

                    }
                }

            }
        }

 

 

위쪽 단면도에서 이동할 수 있는 좌표간 인접행렬을 입력합니다.

↓

// 위쪽 단면도에 속하는 셀들에 대응되는 번호의 정점 쌍에 대해 간선을 추가합니다
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < M; j++) {

                int idx = timeWallCellId[4][i][j];

                for(int dd = 0; dd < 4; dd++) {
                    int nx = i + dx[dd];
                    int ny = j + dy[dd];
                    // 범위를 벗어날 경우 넘어갑니다
                    if(nx < 0 || ny < 0 || nx >= M || ny >= M) continue;
                    // 그렇지 않을 경우 이어줍니다
                    graph[idx][dd] = timeWallCellId[4][nx][ny];
                }
            }
        }

 

위쪽 단면도와 동, 남, 서, 북 단면도를 이어줍니다.

↓

// 동쪽 단면도와 인접한 셀들의 경우
        for(int i = 0; i < M; i++) {
            int idx = timeWallCellId[4][i][M-1]; // 인접한 위쪽 단면도의 셀의 번호
            int idy = timeWallCellId[0][0][M-1-i]; // 인접한 동쪽 단면도의 셀의 번호
            graph[idx][0] = idy;
            graph[idy][3] = idx;
        }
        // 남쪽 단면도와 인접한 셀들의 경우
        for(int i = 0; i < M; i++) {
            int idx = timeWallCellId[4][M-1][i]; // 인접한 위쪽 단면도의 셀의 번호
            int idy = timeWallCellId[1][0][i]; // 인접한 남쪽 단면도의 셀의 번호
            graph[idx][1] = idy;
            graph[idy][3] = idx;
        }
        // 서쪽 단면도와 인접한 셀들의 경우
        for(int i = 0; i < M; i++) {
            int idx = timeWallCellId[4][i][0]; // 인접한 위쪽 단면도의 셀의 번호
            int idy = timeWallCellId[2][0][i]; // 인접한 서쪽 단면도의 셀의 번호
            graph[idx][2] = idy;
            graph[idy][3] = idx;
        }
        // 북쪽 단면도의 경우
        for(int i = 0; i < M; i++) {
            int idx = timeWallCellId[4][0][i]; // 인접한 위쪽 단면도의 셀의 번호
            int idy = timeWallCellId[3][0][M-1-i]; // 인접한 북쪽 단면도의 셀의 번호
            graph[idx][3] = idy;
            graph[idy][3] = idx;
        }

 

평면도에서 시간의 벽이 시작하는 셀의 위치를 활용하여 시간의 방 (동, 남, 서, 북) 면과 미지의 공간 평면도를 이어줍니다.

↓

// 평면도에서 시간의 벽이 시작하는 셀의 행 번호, 열 번호
        int timewallStartx = -1;
        int timewallStarty = -1;

        // 평면도에서 시간의 벽이 시작하는 셀의 위치를 탐색
        outer:
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(spaceMap[i][j] == 3) {
                    timewallStartx = i;
                    timewallStarty = j;
                    break outer;
                }
            }
        }

        // 평면도와 인접하는 단면도 셀들에 대응되는 번호의 정점을 잇는 간선 추가
        // 동쪽 단면도의 경우
        if(timewallStarty + M < N) {
            for(int i = 0; i < M; i++) {
                int idx = timeWallCellId[0][M-1][i];
                int idy = spaceMapCellId[timewallStartx + (M - 1) - i][timewallStarty + M];
                graph[idx][1] = idy;
                graph[idy][2] = idx;
            }
        }
        // 남쪽 단면도의 경우
        if(timewallStartx + M < N) {
            for(int i = 0; i < M; i++) {
                int idx = timeWallCellId[1][M-1][i];
                int idy = spaceMapCellId[timewallStartx + M][timewallStarty + i];
                graph[idx][1] = idy;
                graph[idy][3] = idx;
            }
        }
        // 서쪽 단면도의 경우
        if(timewallStarty > 0) {
            for(int i = 0; i < M; i++) {
                int idx = timeWallCellId[2][M-1][i];
                int idy = spaceMapCellId[timewallStartx + i][timewallStarty - 1];
                graph[idx][1] = idy;
                graph[idy][0] = idx;
            }
        }
        // 북쪽 단면도의 경우
        if(timewallStartx > 0) {
            for(int i = 0; i < M; i++) {
                int idx = timeWallCellId[3][M-1][i];
                int idy = spaceMapCellId[timewallStartx - 1][timewallStarty + (M-1) - i];
                graph[idx][1] = idy;
                graph[idy][1] = idx;
            }
        }

 

 

 

알게된 점

• 좌표에 번호를 할당하고 그 번호를 담는 추가 자료구조를 활용해 문제를 해결할 수 있다.
  (할당된 번호로 인접행렬 구현에 활용)
• 거리 배열로 장애물 처리를 해줄 수 있다 ( 인접행렬을 만들 때 미리 가지 못 하는 좌표를 처리해줄 수 도 있음 )
• 몫 연산, 나머지 연산으로 순회하는 로직을 구현할 수 있다. 
• 방향벡터의 순서를 (동 남 서 북) 과 같이 변경해서 문제 해결에 활용할 수 있다.

 

전체코드

package com.mincheolsong;
import java.util.*;
import java.io.*;

// 시간 이상 현상에 대한 정보를 저장할 구조체
class AbnormalTimeEvent{
    // 시간 이상 현상이 시작점의 행번호, 열번호, 방향, 확장 주기, 시간 이상 현상의 진행여부를 차례로 저장합니다
    int xpos, ypos, direction, cycle, alive;
}

public class Main {

    static final int INF = (int)1e9;

    static int[][] spaceMap; // 미지의 공간의 평면도
    static int[][] spaceMapCellId; // 평면도의 각 셀에 대응하는 그래프 정점의 번호를 저장하는 배열
    static int[][][] timeWall; // 시간의 벽의 단면도
    static int[][][] timeWallCellId; // 시간의 벽의 단면도의 각 셀에 대응하는 그래프 정점의 번호를 저장하는 배열

    static AbnormalTimeEvent[] events;

    // 그래프를 저장할 인접리스트
    static int[][] graph;

    // 타임머신에서 해당 번호의 셀까지 도달하는데 필요한 최소 턴 횟수
    static int[] dist;

    // 그래프 생성 함수
    static void build_graph(int N, int M) {
        int cnt = 0;

        // 각 셀에 대해 대응될 번호를 차례로 부여합니다
        // 평면도 중 시간의 벽이 아닌 부분의 셀들을 순회한 후,
        // 단면도에 속하는 셀들을 단면도의 동쪽 -> 남쪽 -> 서쪽 -> 북쪽 -> 위쪽 순으로 셀들을 순회하면서 번호를 부여합니다
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(spaceMap[i][j] != 3) { // 시간의 벽이 있는 셀이 아닌 경우에만 번호를 부여합니다
                    spaceMapCellId[i][j] = ++cnt;
                }
            }
        }

        // 단면도의 동쪽, 남쪽, 서쪽, 북쪽, 위쪽 순으로 순회하며 셀에 번호를 부여합니다
        for(int t = 0; t < 5; t++) {
            for(int i = 0; i < M; i++) {
                for(int j = 0; j < M; j++) {
                    timeWallCellId[t][i][j] = ++cnt;
                }
            }
        }

        // 부여한 번호의 정점들로 구성된 그래프
        // 정점의 번호에 대응되는 셀과 인접한 셀의 번호를 가지는 정점과 간선으로 연결합니다
        // 최대 4개의 정점과 연결될 수 있습니다
        // 평면도(단면도)에서, 오른쪽으로 인접한 경우 0, 아래쪽으로 인접한 경우 1, 왼쪽으로 인접한 경우 2, 위쪽으로 인접한 경우 3의 인덱스에 저장합니다

        graph = new int[cnt+1][4];
        for(int i = 0; i < cnt+1; i++) {
            Arrays.fill(graph[i], -1);
        }

        // 간선을 추가하는 작업을 위해 사용할 dx, dy 배열
        // 동, 남, 북, 서에 대응되는 순서로 채워져 있습니다
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        // 평면도에 속하는 셀에 대응되는 번호의 정점 쌍에 대해 간선을 추가합니다
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(spaceMap[i][j] != 3) { // 현재 셀에 장애물이 없는 경우

                    int idx = spaceMapCellId[i][j];

                    // 동, 남, 북, 서 순으로 인접한 셀들을 탐색합니다
                    for(int dd = 0; dd < 4; dd++) {
                        int nx = i + dx[dd];
                        int ny = j + dy[dd];

                        // 범위를 벗어나면 넘어갑니다
                        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                        // 셀에 장애물이 있는 경우 넘어갑니다
                        if(spaceMap[nx][ny] == 3) continue;

                        // 그렇지 않은 경우, 이어줍니다
                        graph[idx][dd] = spaceMapCellId[nx][ny];
                    }
                }
            }
        }

        // 단면도의 동쪽, 남쪽, 서쪽, 북쪽에 있는 셀들이 인접할 경우
        // 대응되는 번호의 정점들을 이어줍니다
        for(int t = 0; t < 4; t++) {
            for(int i = 0; i < M; i++) {
                for(int j = 0; j < M; j++) {

                    int idx = timeWallCellId[t][i][j];

                    // 위와 비슷하게 4방향 탐색
                    for(int dd = 0; dd < 4; dd++) {
                        int nx = i + dx[dd];
                        int ny = j + dy[dd];

                        // 행 범위가 넘어갔을 경우 통과
                        if(nx < 0 || nx >= M) continue;

                        // 열 번호가 0보다 작아질 경우, 시계방향순으로 하나 앞에 있는 단면도의 가장 오른쪽 열의 셀과 인접합니다
                        if(ny < 0) {
                            graph[idx][dd] = timeWallCellId[(t+1)%4][nx][M-1];
                        }
                        // 열 번호가 M-1보다 커질 경우, 반시계방향순으로 하나 앞에 있는 단면도의 가장 왼쪽 열의 셀과 인접합니다
                        else if(ny >= M) {
                            graph[idx][dd] = timeWallCellId[(t+3)%4][nx][0];
                        }
                        // 그 외의 경우 평면도의 경우처럼 이어줍니다
                        else {
                            graph[idx][dd] = timeWallCellId[t][nx][ny];
                        }

                    }
                }

            }
        }

        // 위쪽 단면도에 속하는 셀들에 대응되는 번호의 정점 쌍에 대해 간선을 추가합니다
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < M; j++) {

                int idx = timeWallCellId[4][i][j];

                for(int dd = 0; dd < 4; dd++) {
                    int nx = i + dx[dd];
                    int ny = j + dy[dd];
                    // 범위를 벗어날 경우 넘어갑니다
                    if(nx < 0 || ny < 0 || nx >= M || ny >= M) continue;
                    // 그렇지 않을 경우 이어줍니다
                    graph[idx][dd] = timeWallCellId[4][nx][ny];
                }
            }
        }

        // 위쪽 단면도와 인접한 동쪽, 남쪽, 서쪽, 북쪽 단면도의 셀들에 대해
        // 대응되는 번호의 정점을 잇는 간선을 추가합니다

        // 동쪽 단면도와 인접한 셀들의 경우
        for(int i = 0; i < M; i++) {
            int idx = timeWallCellId[4][i][M-1]; // 인접한 위쪽 단면도의 셀의 번호
            int idy = timeWallCellId[0][0][M-1-i]; // 인접한 동쪽 단면도의 셀의 번호
            graph[idx][0] = idy;
            graph[idy][3] = idx;
        }
        // 남쪽 단면도와 인접한 셀들의 경우
        for(int i = 0; i < M; i++) {
            int idx = timeWallCellId[4][M-1][i]; // 인접한 위쪽 단면도의 셀의 번호
            int idy = timeWallCellId[1][0][i]; // 인접한 남쪽 단면도의 셀의 번호
            graph[idx][1] = idy;
            graph[idy][3] = idx;
        }
        // 서쪽 단면도와 인접한 셀들의 경우
        for(int i = 0; i < M; i++) {
            int idx = timeWallCellId[4][i][0]; // 인접한 위쪽 단면도의 셀의 번호
            int idy = timeWallCellId[2][0][i]; // 인접한 서쪽 단면도의 셀의 번호
            graph[idx][2] = idy;
            graph[idy][3] = idx;
        }
        // 북쪽 단면도의 경우
        for(int i = 0; i < M; i++) {
            int idx = timeWallCellId[4][0][i]; // 인접한 위쪽 단면도의 셀의 번호
            int idy = timeWallCellId[3][0][M-1-i]; // 인접한 북쪽 단면도의 셀의 번호
            graph[idx][3] = idy;
            graph[idy][3] = idx;
        }

        // 평면도에서 시간의 벽이 시작하는 셀의 행 번호, 열 번호
        int timewallStartx = -1;
        int timewallStarty = -1;

        // 평면도에서 시간의 벽이 시작하는 셀의 위치를 탐색
        outer:
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(spaceMap[i][j] == 3) {
                    timewallStartx = i;
                    timewallStarty = j;
                    break outer;
                }
            }
        }

        // 평면도와 인접하는 단면도 셀들에 대응되는 번호의 정점을 잇는 간선 추가
        // 동쪽 단면도의 경우
        if(timewallStarty + M < N) {
            for(int i = 0; i < M; i++) {
                int idx = timeWallCellId[0][M-1][i];
                int idy = spaceMapCellId[timewallStartx + (M - 1) - i][timewallStarty + M];
                graph[idx][1] = idy;
                graph[idy][2] = idx;
            }
        }
        // 남쪽 단면도의 경우
        if(timewallStartx + M < N) {
            for(int i = 0; i < M; i++) {
                int idx = timeWallCellId[1][M-1][i];
                int idy = spaceMapCellId[timewallStartx + M][timewallStarty + i];
                graph[idx][1] = idy;
                graph[idy][3] = idx;
            }
        }
        // 서쪽 단면도의 경우
        if(timewallStarty > 0) {
            for(int i = 0; i < M; i++) {
                int idx = timeWallCellId[2][M-1][i];
                int idy = spaceMapCellId[timewallStartx + i][timewallStarty - 1];
                graph[idx][1] = idy;
                graph[idy][0] = idx;
            }
        }
        // 북쪽 단면도의 경우
        if(timewallStartx > 0) {
            for(int i = 0; i < M; i++) {
                int idx = timeWallCellId[3][M-1][i];
                int idy = spaceMapCellId[timewallStartx - 1][timewallStarty + (M-1) - i];
                graph[idx][1] = idy;
                graph[idy][1] = idx;
            }
        }

        return;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N, M, E; // 미지의 공간의 한 변의 길이, 시간의 벽 한 변의 길이, 시간 이상 현상의 개수

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        spaceMap = new int[N][N];
        spaceMapCellId = new int[N][N];
        timeWall = new int[5][M][M];
        timeWallCellId = new int[5][M][M];
        events = new AbnormalTimeEvent[E];

        // 공간의 평면도 입력
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                spaceMap[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 시간의 벽의 동쪽 단면도 입력
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                timeWall[0][i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 시간의 벽의 서쪽 단면도 입력
        // 구현의 편의를 위해서 TimeWall[2][][]에 서쪽 단면도 정보 저장
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                timeWall[2][i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 시간의 벽의 남쪽 단면도 입력
        // 구현의 편의를 위해서 TimeWall[1][][]에 남쪽 단면도 정보 저장
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                timeWall[1][i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 시간의 벽의 북쪽 단면도 입력
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                timeWall[3][i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 시간의 벽의 위쪽 단면도 입력
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                timeWall[4][i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 시간 이상 현상에 대한 정보 입력
        for(int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            events[i] = new AbnormalTimeEvent();
            events[i].xpos = Integer.parseInt(st.nextToken());
            events[i].ypos = Integer.parseInt(st.nextToken());
            events[i].direction = Integer.parseInt(st.nextToken());
            events[i].cycle = Integer.parseInt(st.nextToken());
            if(events[i].direction == 1) events[i].direction = 2;
            else if(events[i].direction == 2) events[i].direction = 1;

            events[i].alive = 1;
        }

        // 공간의 상황에 대응되는 그래프 생성
        build_graph(N, M);

        // 생성된 그래프의 정점의 개수는
        // N*N - M*M + 5*M*M = N*N + 4*M*M 개
        // -1로 배열의 값을 초기화한다.
//        int maxNodes = N*N + 4*M*M + 1;
        dist = new int[graph.length];
        Arrays.fill(dist, -1);

        // 장애물인 경우 도달할 수 없으므로 미리 아주 큰 값으로 세팅합니다
        // 평면도에 있는 장애물의 경우
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(spaceMap[i][j] == 3) continue;
                if(spaceMap[i][j] == 1) {
                    int idx = spaceMapCellId[i][j];
                    dist[idx] = INF;
                }
            }
        }

        // 평면도에서 시간 이상 현상의 시작점도 도달 불가능하므로 장애물과 같이 처리합니다
        for(int i = 0; i < E; i++) {
            int x = events[i].xpos;
            int y = events[i].ypos;
            int idx = spaceMapCellId[x][y];
            dist[idx] = INF;
        }

        // 단면도 위에 있는 장애물의 경우 역시 똑같이 처리합니다
        for(int t = 0; t < 5; t++) {
            for(int i = 0; i < M; i++) {
                for(int j = 0; j < M; j++) {
                    if(timeWall[t][i][j] == 1) {
                        int idx = timeWallCellId[t][i][j];
                        dist[idx] = INF;
                    }
                }
            }
        }

        // BFS를 진행할 큐
        Deque<Integer> q = new ArrayDeque<Integer>();

        int cell_start = -1;
        int cell_end = -1;

        // 탈출구 위치 탐색
        outer1:
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(spaceMap[i][j] == 4) {
                    cell_end = spaceMapCellId[i][j];
                    break outer1;
                }
            }
        }

        // 타임머신의 시작점 탐색
        outer2:
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < M; j++) {
                if(timeWall[4][i][j] == 2) {
                    cell_start = timeWallCellId[4][i][j];
                    break outer2;
                }
            }
        }

        q.offer(cell_start);
        dist[cell_start] = 0;

        int runs = 1;

        while(!q.isEmpty()) {

            // 현재 턴에 확장하는 이상현상이 있으면 영향을 받는 셀을 업데이트합니다
            for(int i = 0; i < E; i++) {
                if(events[i] == null) continue;
                if(events[i].alive == 0) continue; // 더 이상 확산하지 않는 이상 현상이면 넘어갑니다
                if(runs % events[i].cycle != 0) continue; // 지금 턴에 확산하지 않으면 넘어갑니다

                // 이상 현상의 시작점
                int nx = events[i].xpos;
                int ny = events[i].ypos;

                // 이상현상의 방향에 따라 영향을 받는 셀의 좌표를 구합니다
                if(events[i].direction == 0) {
                    ny += (runs / events[i].cycle);
                }
                else if(events[i].direction == 1) {
                    nx += (runs / events[i].cycle);
                }
                else if(events[i].direction == 2) {
                    ny -= (runs / events[i].cycle);
                }
                else {
                    nx -= (runs / events[i].cycle);
                }

                if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
                    events[i].alive = 0;
                    continue;
                }

                // 이상현상이 장애물이나 탈출구, 시간의 벽을 만난 경우, 확산하지 않습니다
                if(spaceMap[nx][ny] != 0) {
                    events[i].alive = 0;
                    continue;
                }

                // 대응되는 셀의 번호는 이제 타임머신이 도달할 수 없습니다
                int idx = spaceMapCellId[nx][ny];
                dist[idx] = INF;
            }


            // 이번턴에 도달 가능한 셀들을 찾습니다
            int size = q.size();

            for(int s=0;s<size;s++) {
                int idx = q.pollFirst();

                for(int i = 0; i < 4; i++) {
                    int idy = graph[idx][i];
                    if(idy == -1) continue; // 해당 방향으로 이동가능한 셀 없는 경우 통과합니다
                    if(dist[idy] != -1) continue; // 이미 최소 턴의 수를 계산한 셀의 경우 통과합니다
                    dist[idy] = runs;
                    q.offer(idy); // 이번에 새로 도달 가능한 셀의 번호를 추가합니다
                }
            }

            // 탈출구에 가기 위해 필요한 최소 턴수를 구했다면, 종료합니다.
            if(dist[cell_end] != -1) {
                break;
            }

            runs+= 1;
        }

        // 정답을 출력합니다.
        // 불가능하면 -1이 출력됩니다
        if(dist[cell_end] == -1 || dist[cell_end] >= INF) {
            System.out.println(-1);
        } else {
            System.out.println(dist[cell_end]);
        }

    }
}