[백준 3055 java 자바] 탈출 (BFS/DFS)

[Gold IV] 탈출 - 3055

문제 링크

성능 요약

메모리: 16608 KB, 시간: 188 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

---

풀이

물길이 퍼지는 조건은 1초당인데, 기존 BFS의 동작에서는 초단위의 반복 활동이 아니기에, 물길을 퍼트리고, 해당 물길 조건에서 고슴도치가 움직일 수 있는 모든 조건을 수행시키는 것을 반복하는게 포인트다.

코드

class Main {
    static String[][] graph; //지도
    static Queue<Node> waterList = new LinkedList<>(); //물길을 담는다
    static Queue<Node> q = new LinkedList<>(); 

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

    static class Node {
        int x;
        int y;

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

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

        int cnt = 0;
    }

    static Node Beaver; //비버의 위치
    static Node Gosum;  //고슴도치의 위치

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        r = Integer.parseInt(strs[0]);
        c = Integer.parseInt(strs[1]);
        graph = new String[r][c];


        //초기화
        for (int i = 0; i < r; i++) {
            strs = br.readLine().split("");
            for (int j = 0; j < c; j++) {
                graph[i][j] = strs[j];
                if (strs[j].equals("*")) {
                    waterList.offer(new Node(i, j)); //물길을 미리 넣어놓는다.
                }
                if (strs[j].equals("D")) Beaver = new Node(i, j); //비버굴의 위치
                if (strs[j].equals("S")) Gosum = new Node(i, j); //고슴도치의 위치
            }
        }
        q.offer(Gosum);//고슴도치의 위치를 미리 넣어놓는다.
        bfs();
        System.out.println("KAKTUS");
    }
    static void bfs() {
        while (!q.isEmpty()) {
            //선제 조건으로 물길 퍼트림. 어차피 물의 다음 예정위치에 고슴도치는 갈 수 없기 때문에,
            //미리 물을 퍼트려놓는다.
            int waterSize = waterList.size(); //1초에 들어있던 전체의 물길을 동작시키는게 포인트.
            for (int t = 0; t < waterSize; t++) {
                Node water = waterList.poll();
                for (int i = 0; i < 4; i++) {
                    int nX = dx[i] + water.x;
                    int nY = dy[i] + water.y;

                    if(nX < 0 || nX >= r || nY < 0 || nY >= c) continue;
                    if (graph[nX][nY].equals(".")) {//물의 다음 위치가 땅이면 물로 만든다.
                        graph[nX][nY] = "*";
                        waterList.offer(new Node(nX, nY));
                    }
                }
            }

            int qSize = q.size(); //1초에 지금 들어있는 모든 경우를 돌린다.
            for (int t = 0; t < qSize; t++) {
                Node G = q.poll();
                for (int i = 0; i < 4; i++) {
                    int nX = dx[i] + G.x;
                    int nY = dy[i] + G.y;

                    if(nX < 0 || nX >= r || nY < 0 || nY >= c) continue;
                    if (graph[nX][nY].equals("D")) {
                        System.out.println(G.cnt+1);
                        System.exit(0);
                    } else if (graph[nX][nY].equals(".")) {
                        graph[nX][nY] = "S";
                        q.offer(new Node(nX, nY, G.cnt + 1));
                    }
                }
            }

        }
    }
}