[백준] 3055 탈출 자바 BFS 문제 풀이 및 정답

문제 요약)

- 고슴도치 위치, 고슴도치 굴 위치, 물 위치, 돌 위치 등이 주어짐

- 고슴도치가 굴에 들어갈 수 있으면 이동거리, 없으면 주어진 문자 출력

 

주의점)

- 예외 조건이 꽤 있는 편(물이 먼저 찰 예정이면 고슴도치는 진입 불가, 물은 고슴도치 굴에 접근 불가 등)

 

풀이)

조건 중 물이 접근 예정인 곳은 고슴도치가 접근할 수 없다는 조건이 있습니다.

따라서, 물을 먼저 q에 넣고 고슴도치 위치를 별도로 저장해서 BFS돌 당시에

물이 먼저 bfs를 돌면서 위치를 선점할 수 있게하면 해당 조건을 만족 시킬 수 있습니다.

 

두 번째로, 고슴도치가 굴에 도착하는지 판단할 수 있도록 고슴도치 굴의 위치는 저장해놓고

map에서 고슴도치가 가는 길은 고슴도치로, 물이 가는 길은 물로 바꿔주면 최종적으로

저장해놨던 고슴도치 굴의 위치에 고슴도치가 들어있는지 판단해보면 알 수 있습니다.

 

정답)

import java.util.*;

public class Escape3055_blog {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static char[][] map;
    static int[][] distance;
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        map = new char[n][m];
        distance = new int[n][m];

        Queue<int[]> q1 = new LinkedList<>(); // 물만 넣어줄 q
        Queue<int[]> q2 = new LinkedList<>(); // 고슴도치 넣어줄 q
        int[] endPoint = new int[2]; // 고슴도치 굴 위치

        for (int i=0; i<n; i++) {
            String str = sc.next();

            for (int j=0; j<str.length(); j++) {
                char word = str.charAt(j);
                map[i][j] = word;
                
                if (word == '*') { // 물인 경우 q1에 넣기
                    q1.offer(new int[] {i, j});
                    distance[i][j] = 1;
                    
                } else if (word == 'S') { // 고슴도치면 q2에 넣기
                    q2.offer(new int[] {i, j});
                    distance[i][j] = 1;
                    
                } else if (word == 'D') { // 고슴도치 굴이면 endPoint에 넣기
                    endPoint = new int[] {i, j};
                }
            }
        }

        BFS(q1, q2);

        if (map[endPoint[0]][endPoint[1]] == 'S') {
            System.out.println(distance[endPoint[0]][endPoint[1]] - 1);
        } else {
            System.out.println("KAKTUS");
        }
    }

    static void BFS(Queue<int[]> q1, Queue<int[]> q2) {
        Queue<int[]> q = new LinkedList<>();
        while(!q1.isEmpty()) { // 반드시 물부터 넣어주기
            q.offer(q1.poll());
        }
        while(!q2.isEmpty()) { // 고슴도치 넣기
            q.offer(q2.poll());
        }

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int curX = current[0];
            int curY = current[1];

            for (int i=0; i<dx.length; i++) {
                int nx = curX + dx[i];
                int ny = curY + dy[i];

                // index에러 방지, 문제에서 주어진 조건 넣기
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (distance[nx][ny] > 0 || map[nx][ny] == 'X' || distance[nx][ny] == 'S' || distance[nx][ny] == '*') continue;
                if (map[curX][curY] == '*' && map[nx][ny] == 'D') continue;

                // 제외할 조건 외에는 q에 넣어서 진행
                q.offer(new int[] {nx, ny});
                distance[nx][ny] = distance[curX][curY] + 1;
                map[nx][ny] = map[curX][curY];
            }
        }
    }
}