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

문제

https://www.acmicpc.net/problem/2665

n*n 바둑판에서 검은 방(벽면)을 뚫어 시작점(0*0)부터 끝점(n-1, n-1)까지 갈 때, 뚫는 벽의 최소 개수를 구하는 문제이다.

풀이

0-1 BFS 알고리즘

이 문제는 0-1 BFS 알고리즘을 사용하여 풀 수 있는 문제다.

 

간선의 가중치가 모두 다를 때 다익스트라로 최단 거리를 찾을 수 있었다면,

간선의 가중치가 다르긴 한데 0과 1밖에 없는 경우 다익스트라보다 더 효율적인 방법으로 0-1 BFS를 쓸 수 있다.

 

이 블로그에 내용이 잘 정리되어있다.

https://krrong.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-0-1-BFS

[알고리즘] 0-1 BFS

 

간단히 설명하면 다익스트라는 우선순위 큐를 활용하여 (시작 노드부터 해당 노드까지의) 최소 거리가 가장 작은 값부터 탐색하도록 했는데

0-1 BFS는 데크를 활용한다. 최소 거리가 늘어나면 데크의 back에, 늘어나지 않았으면 데크의 front에 노드를 삽입하여 최소 거리가 작은 값부터 탐색하도록 만든다. 

 

물론 다익스트라로 구현해도 되는데 다익스트라는 우선순위 큐에 새로운 노드를 넣을 때마다 매번 가중치가 작은 순서대로 유지하기 위해 정렬을 수행한다. 반면 0-1 BFS는 가중치가 늘어나면 데크의 back에 노드를 삽입하고 그대로면 front에 노드를 삽입함으로써 매번 정렬이 수행될 필요가 없어 성능이 더 좋다.

 

문제 풀이는 다음과 같다.

자바 코드 :

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

public class Main {
    static int n;
    static int[][] graph;
    static int[][] dist;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        graph = new int[n][n];
        for(int i=0; i<n; i++){
            String str = br.readLine();
            for(int j=0; j<n; j++){
                char val = str.charAt(j);
                if(val=='0'){
                    graph[i][j] = 1;
                }else{
                    graph[i][j] = 0;
                }

            }
        }

        dist = new int[n][n];
        for(int i=0; i<n; i++)
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        dist[0][0] = 0;

        visited = new boolean[n][n];

        bfs(0, 0);
        System.out.println(dist[n-1][n-1]);

    }

    static void bfs(int x, int y){
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        Deque<Node> deque = new ArrayDeque<>();
        deque.addFirst(new Node(x, y, 0));

        while(!deque.isEmpty()){
            Node now = deque.pollFirst();

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

                if(nx<0 || nx>=n || ny<0 || ny>=n)
                    continue;

                if(!visited[nx][ny]){
                    int newDist = dist[now.x][now.y] + graph[nx][ny];
                    if(dist[nx][ny] > newDist){
                        dist[nx][ny] = newDist;
                    }
                    if(graph[nx][ny]==0){
                        deque.addFirst(new Node(nx, ny, newDist));
                    }else{
                        deque.addLast(new Node(nx, ny, newDist));
                    }
                    visited[nx][ny] = true;
                }
            }

        }
    }
}

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

파이썬 코드 :

from collections import deque
import sys

input = sys.stdin.read
data = input().split()

n = int(data[0])
graph = [[1 if ch == '0' else 0 for ch in data[i+1]] for i in range(n)]

INF = float('inf')
dist = [[INF] * n for _ in range(n)]
dist[0][0] = 0

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs():
    deque_queue = deque([(0, 0, 0)])  # (부순 벽 개수, x, y)
    
    while deque_queue:
        w, x, y = deque_queue.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                new_dist = dist[x][y] + graph[nx][ny]
                
                if dist[nx][ny] > new_dist:
                    dist[nx][ny] = new_dist
                    if graph[nx][ny] == 0:
                        deque_queue.appendleft((new_dist, nx, ny))
                    else:
                        deque_queue.append((new_dist, nx, ny))

bfs()
print(dist[n-1][n-1])