BOJ_1261 : 알고스팟

👉 문제링크

---

---

🔸 문제 분석 🔸

• N*M 미로에서 (1, 1) 부터 (N, M) 까지 가는 최소 비용을 구하는 문제이다.
• 미로는 빈 방과 벽으로 이루어져 있고, 벽을 부수는데 비용이 1 소모된다.

🔸 문제 풀이 🔸

• 가중치가 0과 1로 이루어진 그래프에서 최소 비용 혹은 최단 경로를 구하는 문제라고 볼 수 있다.
• 최단 경로 문제는 다익스트라(Dijkstra) 알고리즘을 많이 사용한다. 첫 번째 풀이에서 사용했다.
  • 다익스트라의 시간 복잡도는 O(E log V) 이다.
  • 노드를 방문해 가며, 가중치가 더 적은 경로가 발견되면 해당 노드부터 다시 경로를 탐색해보는 방법이다.
• 가중치가 0과 1로 이루어진 경우에 0-1 BFS를 사용해서 더 효율적으로 풀이할 수 있다.
  • 0-1 BFS의 시간 복잡도는 O(V + E) 이다.
  • 모든 노드와 경로를 1번씩만 방문한다.
  • 큐 대신 덱을 사용하며 가중치가 0인 경우는 front, 가중치가 1인 경우는 back에 삽입한다.
  • 덱의 front 부터 노드를 꺼내 탐색하며, 최단 경로를 먼저 탐색하는 효과가 생긴다.

🔸 기존 코드 🔸

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean[][] map = new boolean[N][M]; // 맵 정보
        int[][] visited = new int[N][M]; // 방문시 부순 벽의 갯수 최소값

        for (int i = 0; i < N; i++) {

            char[] chars = br.readLine().toCharArray();

            for (int j = 0; j < M; j++) {
                map[i][j] = chars[j] == '0'; // 벽은 false
                visited[i][j] = Integer.MAX_VALUE; // 부순 벽 갯수 초기화
            }
        }

        // BFS
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        Queue<AOJ> que = new ArrayDeque<>();
        que.add(new AOJ(0, 0, 0));
        visited[0][0] = 0;

        int answer = Integer.MAX_VALUE;

        while (!que.isEmpty()) {
            AOJ aoj = que.poll();

            if (aoj.row == N - 1 && aoj.col == M - 1) {
                answer = Math.min(answer, aoj.broken);
            } else {
                for (int i = 0; i < 4; i++) {
                    int r = aoj.row + dx[i];
                    int c = aoj.col + dy[i];
                    if (0 <= r && r < N && 0 <= c && c < M) {
                        if (map[r][c] && visited[r][c] > aoj.broken) {
                            visited[r][c] = aoj.broken;
                            que.add(new AOJ(r, c, aoj.broken));
                        } else if (visited[r][c] > aoj.broken + 1) {
                            visited[r][c] = aoj.broken + 1;
                            que.add(new AOJ(r, c, visited[r][c]));
                        }
                    }
                }
            }
        }

        // Output
        bw.write(Integer.toString(visited[N - 1][M - 1]));
        bw.flush();
    }

    public static class AOJ {
        int row, col, broken;

        public AOJ(int row, int col, int broken) {
            this.row = row;
            this.col = col;
            this.broken = broken;
        }
    }
}

🔸 코드 해석 🔸

• BFS 형식처럼 보이지만, 저장된 비용의 갱신이 일어나면 다시 탐색을 시작하는 다익스트라 알고리즘이 적용되었다.
• 방과 벽 정보는 boolean 이중배열 map으로, 최소 비용을 저장은 int형 이중배열 visited를 사용했다.
• 큐가 모두 빌 때 까지 반복하므로, answer은 사용할 필요가 없었다.

 

🔸 0-1 BFS 코드 🔸

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[][] map = new int[N][M]; // 맵 정보

        for (int i = 0; i < N; i++) {

            char[] chars = br.readLine().toCharArray();

            for (int j = 0; j < M; j++) {
                map[i][j] = Character.getNumericValue(chars[j]);
            }
        }

        // 0-1 BFS
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        Deque<AOJ> dq = new ArrayDeque<>();
        dq.addFirst(new AOJ(0, 0, 0));

        while (!dq.isEmpty()) {
            AOJ aoj = dq.pollFirst();

            if (aoj.row == N - 1 && aoj.col == M - 1) { // Output
                bw.write(Integer.toString(aoj.broken));
                bw.flush();
                break;
            } else {
                for (int i = 0; i < 4; i++) {
                    int r = aoj.row + dx[i];
                    int c = aoj.col + dy[i];
                    if (0 <= r && r < N && 0 <= c && c < M) {
                        if (map[r][c] == 0) {
                            dq.addFirst(new AOJ(r, c, aoj.broken));
                        } else if (map[r][c] == 1) {
                            dq.addLast(new AOJ(r, c, aoj.broken + 1));
                        }
                        map[r][c] = -1; // 방문체크
                    }
                }
            }
        }
    }

    public static class AOJ {
        int row, col, broken;

        public AOJ(int row, int col, int broken) {
            this.row = row;
            this.col = col;
            this.broken = broken;
        }
    }
}

🔸 코드 해석 🔸

• 기존 다익스트라 풀이 코드를 개선해서 0-1 BFS 알고리즘을 적용한 풀이이다.
• 가중치가 0이면 front, 1이면 back에 삽입한다.
• 방문한 노드는 4방 탐색에서 제외하기 위해 맵 정보를 -1로 바꿔버렸다.

---

🔸 end 🔸

•  처음 문제를 풀 때는 N x M 형태의 맵이여서 단순 BFS 최적화 인 줄 알았다.
  • 다시보니 2차원 배열에서 다익스트라 알고리즘을 사용 한 것이었다.
  • 사용한 알고리즘도 제대로 인지를 못했다니... 반성하게 된다.
• 문제를 맞춘 이후에 태그를 확인해보니 0-1 BFS가 있길래 찾아보게 되었다.
  • 언제 본적이 있던 알고리즘인데 어렵지 않으면서 유용해서 바로 포스팅 정리하고, 적용해서 재풀이 했다.
  • 0,1 가중치 그래프에서 다익스트라 보다 좋은 시간 복잡도가 나온다고 알게 되었는데, 확실히 시간이 줄어든 모습이다.