[PS] 백준30894 : 유령의 집 탈출하기(Java)

문제

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

30894번: 유령의 집 탈출하기

---

풀이

3차원 방문체크를 활용한 BFS 풀이

 

접근법

3차원 방문배열을 활용

각 유령들은 시간에 따라 바라보는 방향이 바뀌는데 총 4가지의 서로 다른 맵이 존재함.

이 점을 활용하여 3차원 방문배열을 통해 각 방문배열마다 유령이 바라볼 수 있는 공간들에 대해 미리 전처리한 후 BFS 탐색을 수행.

 

---

소스코드

import java.io.*;
import java.util.*;

//BOJ_30894 유령의 집 탈출하기
public class Main {
    static int N, M, inx, iny, outx, outy, res;
    static int[] dx = new int[]{0,1,0,-1};      //(0 : 오른쪽, 1 : 아래, 2 : 왼쪽, 3 : 위)
    static int[] dy = new int[]{1,0,-1,0};
    static char[][] map;
    static boolean[][][] v;
    static List<int[]> list = new ArrayList();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        st = new StringTokenizer(br.readLine());
        inx = Integer.parseInt(st.nextToken()) - 1;
        iny = Integer.parseInt(st.nextToken()) - 1;
        outx = Integer.parseInt(st.nextToken()) - 1;
        outy = Integer.parseInt(st.nextToken()) - 1;

        map = new char[N][M];
        for(int i=0; i<N; i++) {
            String input = br.readLine();
            for(int j=0; j<M; j++) {
                char idx = input.charAt(j);
                map[i][j] = idx;
                if(idx != '#' && idx != '.') list.add(new int[]{i, j, idx - '0'});
            }
        }

        v = new boolean[4][N][M];       //3차원 방문체크 배열 (유령이 바라보는 4방향에 대해 방문체크 진행)

        /*
        * 전처리 과정
        * 맵관리를 유령이 바라보는 4방향에 대해 3차원 배열로 관리하게 된다면
        * 각 초마다 유령이 바라볼 수 있는 곳들에 대해 미리 방문체크를 해놓는다면
        * BFS로직에서 O(1)의 시간으로 석준이가 해당 방향으로 갈 수 있는지 체크가 가능.
        * */
        for(int i=0; i<4; i++) {
            for(int[] ghost : list) {
                int dist = (ghost[2] + (i % 4)) % 4;        // 현재 초에 대한 유령의 방향
                detactSeokjun(ghost[0], ghost[1], dist, i);
            }
        }

        bfs();

        if(res != 0) System.out.println(res);
        else System.out.println("GG");

    }

    private static void bfs() {
        Queue<int[]> q = new ArrayDeque<>();

        q.offer(new int[]{inx, iny, 0});
        v[0][inx][iny] = true;

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int vIdx = (cur[2] + 1) % 4;      //방문배열 포인터 : 다음 Depth에 대한 포인터

            if(cur[0] == outx && cur[1] == outy) {      //도착지점에 도착했을 경우
                res = cur[2];
                break;
            }

            if(!v[vIdx][cur[0]][cur[1]]) {
                q.offer(new int[]{cur[0], cur[1], cur[2] + 1});     //제자리
            }

            for(int i=0; i<4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if(!rangeValidate(nx, ny)) continue;

                if(map[nx][ny] == '.') {
                    if(!v[vIdx][nx][ny]) {
                        q.offer(new int[]{nx, ny, cur[2] + 1});
                        v[vIdx][nx][ny] = true;
                    }
                }

            }
        }

    }

    private static boolean rangeValidate(int x, int y) {

        if(x<0 || y<0 || x>=N || y>=M) return false;
        return true;
    }

    /*
    * 입력 : 유령의 좌표, 방향, 석준이의 좌표, 방문체크 포인터
    * 로직 : 각 유령이 바라볼 수 있는 공간에 대해 방문체크 진행
    * */
    private static void detactSeokjun(int x, int y, int d, int p) {

        while(true) {
            x += dx[d];
            y += dy[d];

            if(!rangeValidate(x,y)) break;

            if(map[x][y] == '.') v[p][x][y] = true;
            else break;

        }

    }
}

 

 

---

정리

 

첫 4% 틀렸습니다는 방문체크 배열을 int배열을 사용해 한 공간에 대해서는 여러번 방문할 수 없다라는 개념으로 접근했기 때문에 틀림. >> 방문체크 문제

 

18% 시간초과는 방문 확인을 큐에 넣기 전에 확인한게 아니라 큐에서 뺄 때 검사했기 때문.. >> 이 부분이 중요한데 거의 모든 BFS 풀이에서 방문체크의 위치가 중요하다는 점을 알아두었으면 좋겠음!..

 

45% 시간초과의 경우에는 전처리 과정으로 맵을 만들어 놓고 시작한게 아니라 각 BFS의 로직 마다 유령의 바라보는 방향을 Depth를 통해 구한 후 체크해주었기 때문에 틀림. >> 문제에서 유령의 최대개수도 알려주었으면 좀 더 고려해볼 수 있었다고 생각함... (예제에서는 최대 2개밖에 나오지 않아서 몇 개 없겠구나 생각함..)

 

---

보다시피 이번 문제가 상당히 푼 사람이 없었기 때문에 소스코드 참조를 못하는 상황에서 여러번 트라이를 했음...

하지만 여러 번 틀려가면서 내가 작성하고 있는 소스코드에서 어떤 부분이 잘못되었는지를 디버깅하면서 배운 점 또한 많았다고 생각함.