[백준]#11451 팩맨

문제

청호는 팩맨 게임을 하던 도중, 갑자기 팩맨이 분열하여 2마리가 되는 것을 보았다. 이 2마리의 팩맨은 서로 다른 위치에 있지만, 청호의 조이스틱 하나의 조작에 똑같이 반응하였다. 팩맨을 북쪽으로 가도록 조작하면 2마리의 팩맨이 모두 북쪽으로 이동하고, 동쪽으로 가도록 조작하면 역시 둘 다 동쪽으로 이동하였다. 그러나 팩맨은 자신의 앞에 벽이 있으면 이동하지 않는다.

팩맨이 두 마리이면 좋은 점이 있었다. 단 한 번의 움직임으로 2개의 점을 먹을 수 있는 것이다. 그러나, 청호는 두 마리를 동시 조작하려다 보니 머리가 아프기 시작했다. 또한 두 마리가 각각 유령에게 잡아먹히지 않게 하는 것도 만만치 않았다. 만약 팩맨이 유령과 마주치면 청호는 라이프를 하나 잃게 된다. 청호는 라이프가 5개뿐이고, 두 번째 팩맨은 죽으면 다시 되살아나지 못하기 때문에 두 팩맨을 최대한 빨리 한 장소로 합치기로 결심했다. 과연 이것이 가능할까?

입력

첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각각의 테스트 케이스에는

• 첫 번째 줄에 M, N (2 ≤ M, N ≤ 50)이 주어진다. M은 미로의 행 개수, N은 미로의 열 개수를 나타낸다.
• 다음 M개의 줄에 각각 N개의 문자로 미로가 주어진다. 문자는 {P, X, G, .} 중 하나이며 각각
  • P는 팩맨을 의미한다.
  • X는 벽을 의미한다.
  • G는 유령을 의미한다.
  • .은 빈칸을 의미한다.

각 미로에는 정확히 2마리의 팩맨이 존재한다.

출력

각 테스트 케이스에 대해서 정답을 한 줄에 출력한다. 만약 가능할 경우, 팩맨을 조작해야 하는 최소 횟수를 출력한 후, 그 다음에 조작해야 하는 방향을 순서대로 {N, E, S, W}를 사용하여 출력한다. 각각 북쪽, 동쪽, 남쪽, 서쪽을 의미한다. 정답이 여러 개일 경우 아무거나 출력한다. 만약 팩맨을 합치는 것이 불가능하다면 IMPOSSIBLE을 출력한다.

문제를 단순화하기 위해, 유령은 제자리에 가만히 있는다고 가정한다. 또한 팩맨이 화면 끝에서 밖으로 이동하면, 반대편에서 나타난다고 가정한다.

예제 입력 1

3
2 5
.P...
XG.P.
8 8
X...X.X.
X.......
.XXP...X
..X..X..
.PXXXX..
.......X
........
XXXXXXX.
2 2
P.
GP

예제 출력 1

7 WSEESEE
10 EEESSWWWSS
IMPOSSIBLE

풀이

이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static char[][] map;
    static char[] direction = {'N', 'S', 'W', 'E'};
    static int N;
    static int M;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            String[] input = br.readLine().split(" ");
            N = Integer.parseInt(input[0]);
            M = Integer.parseInt(input[1]);
            map = new char[N][M];
            Pair one = null;
            Pair two = null;

            for(int j=0; j<N; j++) {
                String str = br.readLine();
                for(int k=0; k<M; k++) {
                    map[j][k] = str.charAt(k);

                    if(map[j][k]=='P') {
                        if(one==null)
                            one = new Pair(j, k);
                        else
                            two = new Pair(j, k);

                        map[j][k] = '.';
                    }
                }
            }

            bfs(one, two);
        }
    }

    public static void bfs(Pair one, Pair two) {
        Queue<Pack> queue = new LinkedList<>();
        boolean[][][][] visited = new boolean[N][M][N][M];
        queue.add(new Pack(one, two, "", 0));

        while(!queue.isEmpty()) {
            Pack temp = queue.poll();

            if(temp.one.x==temp.two.x && temp.one.y==temp.two.y) {
                System.out.println(temp.cnt+" "+temp.path);
                return;
            }

            for(int i=0; i<4; i++) {
                int nx1 = temp.one.x + dx[i];
                int ny1 = temp.one.y + dy[i];
                int nx2 = temp.two.x + dx[i];
                int ny2 = temp.two.y + dy[i];

                if(nx1<0 || nx1>=N || ny1<0 || ny1>=M) {
                    if(nx1<0)
                        nx1 = N-1;
                    else if(nx1>=N)
                        nx1 = 0;
                    else if(ny1<0)
                        ny1 = M-1;
                    else
                        ny1 = 0;
                }

                if(nx2<0 || nx2>=N || ny2<0 || ny2>=M) {
                    if(nx2<0)
                        nx2 = N-1;
                    else if(nx2>=N)
                        nx2 = 0;
                    else if(ny2<0)
                        ny2 = M-1;
                    else
                        ny2 = 0;
                }

                if(map[nx1][ny1]=='X') {
                    nx1 = temp.one.x;
                    ny1 = temp.one.y;
                }

                if(map[nx2][ny2]=='X') {
                    nx2 = temp.two.x;
                    ny2 = temp.two.y;
                }

                if(visited[nx1][ny1][nx2][ny2] || map[nx1][ny1]=='G' || map[nx2][ny2]=='G') continue;
                visited[nx1][ny1][nx2][ny2] = true;

                queue.add(new Pack(new Pair(nx1, ny1), new Pair(nx2, ny2), temp.path+direction[i], temp.cnt+1));
            }
        }

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

    public static class Pack {
        Pair one;
        Pair two;
        String path;
        int cnt;

        public Pack(Pair one, Pair two, String path, int cnt) {
            this.one = one;
            this.two = two;
            this.path = path;
            this.cnt = cnt;
        }
    }

    public static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}