[백준] 16441번 : 아기돼지와 늑대

16441번: 아기돼지와 늑대

---

[BFS]

빙판('+')만 주의하면 될 문제인줄 알고 섯불리 제출했다가 오답처리를 당했다. 그 이유는 조금 뒤에서 설명하고 우선 문제의 접근법은, 문제에서 주어진 입력을 받으며 늑대의 위치를 기억한다. 그리고 BFS 함수의 인자로 늑대들의 위치를 준다

 

늑대들의 위치에서 각자 BFS를 수행하는데, 빙판('+')을 만나면 산('#')이나 초원('.')을 만날 때 까지 쭉 미끄러진다. 이 부분을 구현하는 메서드는 다음과 같다.

    /* dir: 미끄러지는 방향(상,하,좌,우) */
    static Point sliding(int y, int x, int dir){

        while(true){
            y += Y[dir];
            x += X[dir];

            visit[y][x][dir] = true;
            /* 산을 마주하면 한칸 뒤를 반환 */
            if(map[y][x] == '#')
                return new Point(y - Y[dir], x - X[dir], dir);

            /* 초원을 마주하면 그대로 반환 */
            if(map[y][x] == '.')
                return new Point(y, x, dir);
        }
    }

빙판의 좌표를 주면 해당 방향으로 미끄러지며 방문처리를 한다. 산이나 초원을 만나면 위치를 반환하는데, 산을 만나면 산 앞에서 멈춰서야하고, 초원을 만나면 초원 땅을 밟아야 하므로 반환하는 위치가 조금 다르다.

 

이것만 주의해서 제출하면 오답처리를 받는다. 그 이유는 다른 곳은 몰라도 빙판('+')은 다시 방문할 수 있어야한다. 무슨 말인지 다음 예시를 한번 보도록 하자.

#	#	#	#	#	#	#
#	.	W	+	+	.	#
#	#	.	#	#	#	#
#	.	+	.	.	.	#
#	.	+	#	#	#	#
#	.	+	#	#	#	#
#	#	#	#	#	#	#

위의 예시에서 (4, 3) 빙판을 밟으면 밑으로 쭉 미끄러진다. 이때 (4, 3), (5, 3), (6, 3)빙판은 모두 방문한 상태이다. 이제 좌측 초원으로 이동해서 (4, 4)초원으로 이동하려는데 (4, 3) 빙판은 이미 방문한 상태라 다시 갈 수 없는 상태이다. 내가 간과했던 부분이 이것이었고 이를 해결하기 위해 visit를 3차원 배열로 선언했다.

 

boolean[ ][ ][ ] visit = new boolean[101][101][4]

 

즉 상 하 좌 우 모든 방향에서 방문할 수 있도록 한 것이다. 다른 정점(., W, #)같은 경우는 방향에 크게 구애받지 않지만, 빙판은 다르므로 유의한다. 참고로 저 예시에서 안전한 곳 'P'는 존재하지 않는다.

 

나머지 사항은 코드와 주석을 보면 이해에 도움이 될 것 같다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Point{
        int y, x, dir;
        public Point(int yy, int xx, int d){
            y=yy;
            x=xx;
            dir=d;
        }
    }

    static int n, m;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static char[][] map = new char[101][101];
    static boolean[][][] visit = new boolean[101][101][4];

    /* dir: 미끄러지는 방향(상,하,좌,우) */
    static Point sliding(int y, int x, int dir){

        while(true){
            y += Y[dir];
            x += X[dir];

            visit[y][x][dir] = true;
            /* 산을 마주하면 한칸 뒤를 반환 */
            if(map[y][x] == '#')
                return new Point(y - Y[dir], x - X[dir], dir);

            /* 초원을 마주하면 그대로 반환 */
            if(map[y][x] == '.')
                return new Point(y, x, dir);
        }
    }
    static boolean isVisit(int y, int x){
        for(int i=0; i<4; i++)
            if(visit[y][x][i])
                return false;

        return true;
    }

    static void BFS(List<Point> list){
        Queue<Point> Q = new LinkedList<>();

        list.stream().forEach(p -> {
            visit[p.y][p.x][0] = true;
            Q.add(new Point(p.y, p.x, 0));
        });

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx][a] || map[ny][nx] == '#') continue;

                visit[ny][nx][a] = true;
                
                /* 다음 정점이 빙판('+') */
                if(map[ny][nx] == '+'){
                    /* 빙판을 미끄러져 도착하는 곳의 좌표 반환 */
                    Point nextP = sliding(ny, nx, a);
                    Q.add(new Point(nextP.y, nextP.x, a));
                }
                /* 다음 정점이 초원('.') */
                else
                    Q.add(new Point(ny, nx, a));
            }
        }
    }

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

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

        List<Point> list = new ArrayList<>();

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=m; j++){

                map[i][j] = str[j-1];

                if(map[i][j] == 'W')
                    list.add(new Point(i, j, 0));
            }
        }

        BFS(list);

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                if(map[i][j] == '.'){
                    /* 안전한 곳(늑대가 방문하지 않은 곳) */
                    if(isVisit(i, j))
                        sb.append('P');
                    /* 늑대가 방문한 곳 */
                    else
                        sb.append('.');
                }
                /* 나머지 */
                else
                    sb.append(map[i][j]);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}