[BFS/자바] 코드트리 IL. 비를피하기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

위 문제는 가중치가 1로 동일한 경우에서의 최단 거리를 묻는 문제이므로 BFS를 돌리면 된다고 느낄 수 있다.

 

대표적인 유형의 문제인 걸로 느껴지는데, 지금 뇌가 정지한건지 도저히 내가 어디가 틀린지 모르겠다...

일단 내 풀이는 맞을 가망이 없었고, 아무리 봐도 모르겠어서 일단은 답안을 이해한 뒤에 내 방식대로 고쳐서 작성해 보았다.

 

내 풀이(틀린 풀이)

나는 인간이 있는 좌표로부터 최단거리에 있는 대피소를 BFS로 찾고, 그 최단 거리를 ans라는 정답 배열의 인간 좌표에 입력해주는 방식으로 수행했다. 하지만 절대 답을 구할 수 없었다... 머리로 아무리 생각해봐도 어디서 논리가 삐끗한건지 아직까지는 발견할 수 없었따...

public class 비를피하기 {
    private static int n, h, m;
    private static int step;
    private static int[][] arr;
    private static boolean[][] visited;
    private static int[][] ans;
    private static Queue<Pair> nextPos = new LinkedList<>();
    private static Queue<Pair> startPos = new LinkedList<>();


    private static class Pair {
        private int x;
        private int y;

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

    private static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < n;
    }

    private static boolean canGo(int y, int x) {
        return inRange(y, x) && arr[y][x] != 1 && !visited[y][x];
    }

    private static void bfs(Pair start) {
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        int startY = start.y;
        int startX = start.x;
        nextPos.add(new Pair(startY, startX));
        visited[startY][startX] = true;

        while (!nextPos.isEmpty()) {
            Pair now = nextPos.poll();
            int nowY = now.y;
            int nowX = now.x;
            for (int i = 0; i < 4; i++) {
                int newY = nowY + dy[i];
                int newX = nowX + dx[i];
                if (canGo(newY, newX)) {
                    if (arr[newY][newX] == 3) {
                        ans[startY][startX] = step + 1;
                        return;
                    } else {
                        visited[newY][newX] = true;
                        nextPos.add(new Pair(newY, newX));
                    }
                }
            }
            step++;
        }
        visited = new boolean[n][n];
        step = 0;
        ans[startY][startX] = -1;
    }



    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());
        h = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][n];
        ans = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(st.nextToken());
                arr[i][j] = num;
                if (num == 2) {
                    startPos.add(new Pair(i, j));
                }
            }
        }

        for (Pair p : startPos) {
            visited = new boolean[n][n];
            step = 0;
            bfs(p);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }

    }
}

 

정답 풀이

이 풀이는 전형적인 "BFS로 최단거리 구하기"를 활용한 로직으로, 내 로직보다 훨씬 깔끔하다. 답안에서 요구하는 것은 인간이 있는 좌표에 그 인간이 도달할 수 있는 최단거리의 shelter 까지의 거리를 출력하는 것이므로, 오히려 shelter에서부터 인간 좌표까지의 거리를 구하는 steps 배열을 활용하였다. 필요한 0 또는 -1 처리는 출력 단계에서 arr 값과 visited 값을 이용하여 처리해 주었다.

 

또한 내 로직보다 훨씬 깔끔했던 점은, BFS 알고리즘의 특징을 정확히 이해하여 한번에 starting points의 좌표를 전부 입력해둔 상태에서 한번에 BFS를 돌렸다는 점이다. 처음에 머릿속으로 이해할 때에는 인간당 하나하나 BFS를 수행해야 하나 싶었는데, 다시 생각해보니 각각 visited를 이용하여 각 기점으로부터 최단 거리만 steps에 기록될 것이니 한번에 돌려도 답을 구하는 것에 전혀 문제가 없음을 이해할 수 있었다.

 

숨 좀 고른 뒤에 내 로직이 뭐가 틀린건지 알아보도록 해야겠다.

public class 비를피하기_정답공부 {
    private static int n, h, m;
    private static int[][] arr;
    private static boolean[][] visited;
    private static Queue<Pair> q = new LinkedList<>();
    private static Queue<Pair> shelters = new LinkedList<>();
    private static int[][] steps;

    private static class Pair {
        private int x, y;

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


    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());
        h = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][n];
        visited = new boolean[n][n];
        steps = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (num == 3) {
                    shelters.add(new Pair(i, j));
                }
                arr[i][j] = num;
            }
        }

        for (Pair shelter : shelters) {
            q.add(shelter);
            visited[shelter.y][shelter.x] = true;
            steps[shelter.y][shelter.x] = 0;
        }

        bfs();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] != 2) {
                    System.out.print(0 + " ");
                } else {
                    if (!visited[i][j]) {
                        System.out.print(-1 + " ");
                    } else {
                        System.out.print(steps[i][j] + " ");
                    }
                }
            }
            System.out.println();
        }
    }

    private static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < n;
    }

    private static boolean canGo(int y, int x) {
        return inRange(y, x) && arr[y][x] != 1 && !visited[y][x];
    }

    private static void bfs() {
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        while (!q.isEmpty()) {
            Pair now = q.poll();
            int nowX = now.x;
            int nowY = now.y;
            for (int i = 0; i < 4; i++) {
                int newY = nowY + dy[i];
                int newX = nowX + dx[i];
                if (canGo(newY, newX)) {
                    steps[newY][newX] = steps[nowY][nowX] + 1;
                    visited[newY][newX] = true;
                    q.add(new Pair(newY, newX));
                }
            }
        }
    }
}