백준 30894 (유령의 집) - java

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

30894번: 유령의 집 탈출하기

 

문제

오랜만에 놀이공원에 놀러 가기로 한 석준이는 친구들과 다음과 같은 대화를 나누었습니다.

• 친구A: 유령의 집은 너무 무서울 것 같지 않아? 그냥 롤러코스터 타러 가자...
• 석준: 에이~ 유령의 집이 뭐가 무서워? 줄도 없는데 빨리 들어갔다 나오자!
• 친구B: 그래? 그러면 네가 앞장서서 가면 되겠다. 잘 부탁해~
• 석준: ....

사실 석준이는 누구보다도 유령을 무서워하지만, 이미 허세를 부려버려 돌이킬 방법이 없었습니다.

세로 N칸, 가로 M칸 크기의 유령의 집은 다음과 같이 구성되어 있습니다.

• 빈칸(.): 석준이가 움직일 수 있는 공간을 의미합니다.
• 벽(#): 석준이가 움직일 수 없는 공간을 의미합니다.
• 유령(0, 1, 2, 3): 각 숫자는 유령이 바라보는 초기 방향을 의미합니다. (0 : 오른쪽, 1 : 아래, 2 : 왼쪽, 3 : 위)

어떤 유령이 바라보는 방향에 벽이나 다른 유령이 존재하는 경우, 시야가 가로막혀 그 뒤의 공간은 볼 수 없습니다. 단, 유령의 시야가 가로막히지 않았고 바라보는 방향에 석준이가 있다면, 유령은 거리에 상관없이 석준이를 발견할 수 있습니다. 각 유령은 매초 시계 방향으로 90°도씩 회전하며, 회전하는 동안에는 석준이를 볼 수 없습니다.

석준이는 매초 상하좌우로 인접한 빈칸으로 이동하거나 제자리에 머무를 수 있습니다.

놀이공원 아르바이트 경험이 있던 석준이는 유령의 위치와 지도를 모두 알고 있었고, 어떤 유령에게도 발견되지 않고 최대한 빨리 탈출할 계획을 세우려 합니다.

이미 긴장감에 휩싸여 머리가 새하얘진 석준이를 위해, 여러분이 그 방법을 대신 찾아주세요.

 

유형 : BFS + 탐색 최적화

 

접근 방식

• 우선 유령은 움직이지 않는다. 그리고 매초 보는 방향에 따라 석준이의 이동이 제한된다.
• 위 문제를 처음 보고 다음과 같은 사고를 한다면 위험할 수 있다.
  • 다음 방향을 고려하여 탐색을 진행할 때 근처에 유령의 시야가 잡히는지 '반복문'으로 봐야지 !
  • 위 방법으로 문제를 푼다면 무조건 시간 초과이다. 그리고 굳이 이럴 필요가 없다는 것을 말하고 싶다.
• 유령의 시야는 4가지 방향을 가지고 있다. (0 - > 1 -> 2 -> 3) 그 다음은 ? 다시 0이다. 즉 순환이라는 것이다.
• 좌표계에 따라 유령이 보는 시야는 총 4가지 종류가 있다는 것이다.
  • 미리 유령의 시야를 boolean 배열로 만들어 놓는다면 굳이 매번 탐색시 또 반복문을 돌리지 않아도 된다.
  • 다른 말로 4초마다 유령의 시야가 다시 돌아온다는 것이다.
• 마지막으로 방문 배열에 대해 얘기 하겠다.
  • BFS를 진행할 때 방문 배열을 [n][m][4]로 지정하여 돌아오는 시야마다 해당 위치에 이미 방문한 적이 있는 지 확인한다.

makeSight

 static void makeSight(Queue<Node> q){

    int nx=0,ny=0;
    int idx = 0;
        
    // 방향이 총 4개이므로 4번 반복문으로 시야 배열 초기화
    for(int i=0;i<=3;i++){
        int size = q.size();

        while(size != 0){
            Node cur = q.poll();
            size -= 1;
            sight[cur.x][cur.y][i] = true; // 유령의 위치는 항상 이동 불가능한 고정 위치이다.
            idx= 1;

            while(true){
                nx = cur.x + (idx * dx[cur.d]);
                ny = cur.y + (idx * dy[cur.d]); // 전방이 뚫려 있는 한 끝까지 볼 수 있다.

                if(nx < 1 || nx > n || ny < 1 || ny > m)
                    break; // 좌표계 바깥으로 나간 경우

                if(board[nx][ny] =='#')
                    break; // 벽

                if(board[nx][ny] >= '0' && board[nx][ny] <= '3')
                    break; // 다른 유령
 
                sight[nx][ny][i] = true; // 해당 좌표는 유령의 시야에 걸린다.
                idx += 1;
            }

            q.add(new Node(cur.x,cur.y,changeDir(cur.d))); // 해당 유령이 다음 방향으로 볼때를 위해
            }
        }
    }

    // 방향 전환 메서드 (0 -> 1 -> 2 -> 3 -> 0) 순환
    static int changeDir(int cur){
        if(cur == 3)
            return 0;

        return cur + 1;
    }

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int sx = 0,sy = 0,ex = 0,ey = 0;

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

    static char[][] board;

    static boolean[][][] sight;

    // 0 : 오른쪽, 1 : 아래, 2 : 왼쪽, 3 : 위

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(bf.readLine(), " ");
        sx = Integer.parseInt(st.nextToken());
        sy = Integer.parseInt(st.nextToken());
        ex = Integer.parseInt(st.nextToken());
        ey = Integer.parseInt(st.nextToken());

        board = new char[n+1][m+1];
        sight = new boolean[n+1][m+1][4];

        Queue<Node> ghost = new LinkedList<>();

        for(int i=1;i<=n;i++){
            String line = bf.readLine();

            for(int j=1;j<=m;j++){
                board[i][j] = line.charAt(j-1);

                if(board[i][j] >= '0' && board[i][j] <= '3'){
                    ghost.add(new Node(i,j,board[i][j] - '0'));
                }
            }
        }

        makeSight(ghost);


        search();

        bf.close();
    }

    static void search(){
        Queue<Node> q = new LinkedList<>();
        int[][][] v = new int[n+1][m+1][4];
        q.add(new Node(sx,sy,0));
        v[sx][sy][0] = 1;

        while(!q.isEmpty()){
            Node cur = q.poll();

            if(cur.x == ex && cur.y == ey){
                System.out.println(cur.d);
                return;
            }

            for(int i=0;i<5;i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                int curSight = (cur.d + 1) % 4 ;

                if(nx < 1 || nx > n || ny < 1 || ny > m)
                    continue; // 바깥으로 나간 경우

                if(board[nx][ny] == '#')
                    continue; // 벽인 경우

                if(sight[nx][ny][curSight])
                    continue; // 시야에 잡히는 경우

                if(v[nx][ny][curSight] > 0){
                    continue; // 이미 더 적은 시간에 해당 좌표를 방문한 적 있는 경우
                }

                v[nx][ny][curSight] = v[cur.x][cur.y][cur.d % 4] + 1;
                q.add(new Node(nx,ny,cur.d + 1));
            }
        }

        System.out.println("GG");
    }

    static void makeSight(Queue<Node> q){

        int nx=0,ny=0;
        int idx = 0;
        
        // 방향이 총 4개이므로 4번 반복문으로 시야 배열 초기화
        for(int i=0;i<=3;i++){
            int size = q.size();

            while(size != 0){
                Node cur = q.poll();
                size -= 1;
                sight[cur.x][cur.y][i] = true; // 유령의 위치는 항상 이동 불가능한 고정 위치이다.
                idx= 1;

                while(true){
                    nx = cur.x + (idx * dx[cur.d]);
                    ny = cur.y + (idx * dy[cur.d]); // 전방이 뚫려 있는 한 끝까지 볼 수 있다.

                    if(nx < 1 || nx > n || ny < 1 || ny > m)
                        break; // 좌표계 바깥으로 나간 경우

                    if(board[nx][ny] =='#')
                        break; // 벽

                    if(board[nx][ny] >= '0' && board[nx][ny] <= '3')
                        break; // 다른 유령
 
                    sight[nx][ny][i] = true; // 해당 좌표는 유령의 시야에 걸린다.
                    idx += 1;
                }

                q.add(new Node(cur.x,cur.y,changeDir(cur.d))); // 해당 유령이 다음 방향으로 볼때를 위해
            }
        }
    }

    // 방향 전환 메서드 (0 -> 1 -> 2 -> 3 -> 0) 순환
    static int changeDir(int cur){
        if(cur == 3)
            return 0;

        return cur + 1;
    }

}
class Node{
    int x;
    int y;
    int d;

    Node(int x,int y,int d){
        this.x = x;
        this.y = y;
        this.d = d;
    }
}