[백준 / Java] 2665. 미로만들기

문제

문제 링크

---

풀이

이 문제는 (0, 0) ~ (N-1, N-1)로 가는데 검은 방을 흰 방으로 최소한으로 바꾸면서 갔을 때, 방 색을 바꾼 횟수를 구하는 문제입니다.
즉, 방의 색을 바꾸는 횟수를 가중치로 생각했을 때, 가중치를 최소화하면서 끝 방까지 가는 경우를 구하면 됩니다.
만약 일반 bfs처럼 푼다면 (N-1, N-1)에 가장 먼저 도달했을 때 방의 색을 바꾼 횟수가 최소가 아닐 수 있습니다.

예시: 아래의 경우, 방 색을 전혀 바꾸지 않고도 끝 방에 갈 수 있지만, 방문하는 순서에 따라 방 색을 바꾸는 루트로 가장 먼저 N-1, N-1에 도달할 수 있음

따라서 이 문제에서는 흰 방으로 이동하는 것은 가중치가 0, 검은 방으로 이동하는 것은 가중치가 1이고 큐에 그 칸의 정보를 넣었을 때 가중치가 더 작은 칸이 먼저 큐에서 나오는 것이 보장이 되어야 합니다. (방을 가장 덜 바꾼 경우가 가장 먼저 (N-1, N-1)에 도달할 수 있도록)

그걸 보장해주는 방법으로 크게 2가지가 있을 수 있는데,

1. 가중치가 작은게 먼저 poll() 되도록 PriorityQueue 사용
2. 흰방으로 가는 경우는 deque의 앞에 넣고, 검은 방으로 가는 경우는 deque의 뒤에 넣고 deque의 앞에서부터 poll()

처음에 저는 위의 풀이로 풀었는데, 나중에 다른 분의 코드를 보고 2번 풀이가 더 좋다고 느꼈습니다.
두 가지 방법 다 알아보도록 하겠습니다.

풀이 1. PriorityQueue 사용

  static class Node implements Comparable<Node> {
    int y, x, c;
    Node(int y, int x, int c) {
      this.y = y;
      this.x = x;
      this.c = c;
    }

    @Override
    public int compareTo(Node n) {
      return this.c - n.c;
    }
  }

dp[i][j]의 값은 (i, j) 방에 오기까지 방 색을 최소로 바꾼 그 횟수입니다.
초기에는 모두 int 범위 최대값인 Integer.MAX_VALUE로 설정해줍니다.

    for(int i=0; i<N; ++i) {
      for(int j=0; j<N; ++j) {
        dp[i][j] = Integer.MAX_VALUE;
      }
    }

bfs(라고 써있지만 사실상 다익스트라) 코드

  private static int bfs() {
    PriorityQueue<Node> q = new PriorityQueue<>();
    q.add(new Node(0, 0, 0));
    dp[0][0] = 0;
    int ans = Integer.MAX_VALUE;

    while(!q.isEmpty()) {
      Node cur = q.poll();

      if(cur.y == N-1 && cur.x == N-1) {
        ans = Math.min(cur.c, ans);
      }

      for(int i=0; i<4; ++i) {
        int ny = cur.y + dy[i];
        int nx = cur.x + dx[i];
        if(ny < 0 || nx < 0 || nx >= N || ny >= N) continue;

        if(map[ny][nx] == 0) { // 검은색
          if(dp[ny][nx] > cur.c + 1) {
            dp[ny][nx] = cur.c + 1;
            q.add(new Node(ny, nx, cur.c + 1));
          }
        } else { // 흰색
          if(dp[ny][nx] > cur.c) {
            dp[ny][nx] = cur.c;
            q.add(new Node(ny, nx, cur.c));
          }
        }
      }
    }
    return ans;
  }

Node 클래스에 compareTo 메소드를 아래와 같이 정의해줬기 때문에 PriorityQueue에 Node를 넣으면 c값이 작은 것이 Pq의 가장 위에 위치하게 됩니다.

    @Override
    public int compareTo(Node n) {
      return this.c - n.c;
    }

새로운 노드를 방문하면서 dp[ny][nx]의 값을 최소값으로 갱신해줍니다.

      for(int i=0; i<4; ++i) {
        int ny = cur.y + dy[i];
        int nx = cur.x + dx[i];
        if(ny < 0 || nx < 0 || nx >= N || ny >= N) continue;

        if(map[ny][nx] == 0) { // 검은색
          if(dp[ny][nx] > cur.c + 1) {
            dp[ny][nx] = cur.c + 1;
            q.add(new Node(ny, nx, cur.c + 1));
          }
        } else { // 흰색
          if(dp[ny][nx] > cur.c) {
            dp[ny][nx] = cur.c;
            q.add(new Node(ny, nx, cur.c));
          }
        }

마지막에 dp[N-1][N-1]에 남아있는 값이 최소값이 될 것입니다.

칸의 개수를 M개라고 하면, 이 풀이의 시간복잡도는 대략 (Mlog(M))이 됩니다.
(각 칸을 방문하는 시간 복잡도 O(M) * pq에 Node를 넣을 때마다 정렬하는 시간 복잡도 O(logM))

---

풀이 2. 0-1 bfs (Deque 사용)

가중치가 0 또는 1만 있는 상황에서는 다익스트라를 쓰지 않고 0-1 bfs 방식으로도 풀 수 있습니다.

0-1 bfs란, bfs 함수 내에서 양방향에서 값을 넣고 뺄 수 있는 덱 자료구조를 쓰는 방법입니다.
가중치가 더 적은 루트가 먼저 덱에서 나오는 것을 보장해주기 위해서 흰 방에 방문할 때의 Node는 덱의 앞 쪽에, 검은 방에 방문할 때의 Node는 덱의 뒷쪽에 넣어주고, 덱의 앞에서만 Node를 꺼내주면 됩니다.
그러면 흰방을 통해 가는 루트를 우선적으로 탐색하는 것이 보장됩니다.

칸의 개수가 M개라고 할때, O(M)의 시간 복잡도로 해결할 수 있습니다. (다익스트라보다 효율적)

0-1 bfs 코드

  private static int bfs() {
    Deque<int[]> dq = new LinkedList<>();
    boolean[][] vis = new boolean[N][N];
    dq.addFirst(new int[] {0, 0, 0}); // y, x, 흰색으로 바꾼 개수
    vis[0][0] = true;

    while(!dq.isEmpty()) {
      int[] cur = dq.pollFirst();
      int y = cur[0];
      int x = cur[1];
      int c = cur[2];

      if(y == N-1 && x == N-1) return c;

      for(int i=0; i<4; ++i) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
        if(vis[ny][nx]) continue;

        vis[ny][nx] = true;

        if(arr[ny][nx] == 0) { // 검은색
          dq.addLast(new int[] {ny, nx, c+1});
        } else { // 흰색
          dq.addFirst(new int[] {ny, nx, c});
        }
      }
    }

    return -1;
  }

---

전체 코드

1. 다익스트라(PriorityQueue) 풀이

import java.io.*;
import java.util.*;

class Main {
  static int N, K;
  static int[][] map;
  static int[][] dp;
  static int[] dy = {1, -1, 0, 0};
  static int[] dx = {0, 0, -1, 1};
  static class Node implements Comparable<Node> {
    int y, x, c;
    Node(int y, int x, int c) {
      this.y = y;
      this.x = x;
      this.c = c;
    }

    @Override
    public int compareTo(Node n) {
      return this.c - n.c;
    }
  }

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

    N = Integer.parseInt(br.readLine());
//    K = N * N;
    map = new int[N][N];
    dp = new int[N][N];

    for(int i=0; i<N; ++i) {
      String[] line = br.readLine().split("");
      for(int j=0; j<N; ++j) {
        map[i][j] = Integer.parseInt(line[j]);
      }
    }



    for(int i=0; i<N; ++i) {
      for(int j=0; j<N; ++j) {
        dp[i][j] = Integer.MAX_VALUE;
      }
    }

    System.out.println(bfs());

  }
  private static int bfs() {
    PriorityQueue<Node> q = new PriorityQueue<>();
    q.add(new Node(0, 0, 0));
    dp[0][0] = 0;
    int ans = Integer.MAX_VALUE;

    while(!q.isEmpty()) {
      Node cur = q.poll();

      if(cur.y == N-1 && cur.x == N-1) {
        ans = Math.min(cur.c, ans);
      }

      for(int i=0; i<4; ++i) {
        int ny = cur.y + dy[i];
        int nx = cur.x + dx[i];
        if(ny < 0 || nx < 0 || nx >= N || ny >= N) continue;

        if(map[ny][nx] == 0) { // 검은색
          if(dp[ny][nx] > cur.c + 1) {
            dp[ny][nx] = cur.c + 1;
            q.add(new Node(ny, nx, cur.c + 1));
          }
        } else { // 흰색
          if(dp[ny][nx] > cur.c) {
            dp[ny][nx] = cur.c;
            q.add(new Node(ny, nx, cur.c));
          }
        }
      }
    }
    return ans;
  }
}

2. 0-1 bfs 풀이

import java.io.*;
import java.util.*;

class Main {
  static int N;
  static int[][] arr;
  static int[] dy = {1, -1, 0, 0};
  static int[] dx = {0, 0, 1, -1};
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    N = Integer.parseInt(br.readLine());
    arr = new int[N][N];
    for(int i=0; i<N; ++i) {
      String line = br.readLine();
      for(int j=0; j<N; ++j) {
        arr[i][j] = line.charAt(j) - '0';
      }
    }

    System.out.println(bfs());
  }

  private static int bfs() {
    Deque<int[]> dq = new LinkedList<>();
    boolean[][] vis = new boolean[N][N];
    dq.addFirst(new int[] {0, 0, 0}); // y, x, 흰색으로 바꾼 개수
    vis[0][0] = true;

    while(!dq.isEmpty()) {
      int[] cur = dq.pollFirst();
      int y = cur[0];
      int x = cur[1];
      int c = cur[2];

      if(y == N-1 && x == N-1) return c;

      for(int i=0; i<4; ++i) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
        if(vis[ny][nx]) continue;

        vis[ny][nx] = true;

        if(arr[ny][nx] == 0) { // 검은색
          dq.addLast(new int[] {ny, nx, c+1});
        } else { // 흰색
          dq.addFirst(new int[] {ny, nx, c});
        }
      }
    }

    return -1;
  }
}