[백준]2665: 미로만들기 - JAVA

[백준]2665: 미로만들기

www.acmicpc.net/problem/2665

2665번: 미로만들기

풀이

BFS + 다익스트라를 활용하여 풀었다. 

 

첫 노드에서 오른쪽 아래 노드로 가는 최단 거리 중에서 검은색 벽을 가장 적게 바꾸는 방법의 횟수를 출력하는 문제로 이전에 풀었던 '벽 부수고 이동하기'와 유사한 문제였다.

 

검은색 벽을 흰색 벽으로 바꾸는 최소 횟수를 누적하여 계산하며 탐색하기 위해 다익스트라 방법을 사용하였다. dist배열을 사용하여 현재 위치의 가장 최소 횟수를 저장할 수 있도록 하였다.

 

현재 거리 보다 더 적은 횟수로 이동할 수 있는 방법이 있다면 그 방향으로 이동시켜 주었다. 이때 board가 1이면 횟수를 더해주지 않았고, board가 0이면 흰색으로 변경해 주어야 하므로 횟수를 누적하여 더해주었다.

 

코드

import java.util.*;
 
public class Main {
    
    static int n;
    static int[][] board;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] dist;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
    
        n = scan.nextInt();
        scan.nextLine();
        board = new int[n][n];
        dist = new int[n][n];
        for(int i = 0; i < n; i++) {
            String temp = scan.nextLine();
            for(int j = 0; j < n; j++) {
                board[i][j] = temp.charAt(j) - '0';
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
        
        bfs();
        System.out.println(dist[n - 1][n - 1]);
    }
    
    public static void bfs() {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(0, 0));
        dist[0][0] = 0;
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                if(nx >= 0 && ny >= 0 && nx < n && ny < n && dist[nx][ny] > dist[current.x][current.y]) {
                    if(board[nx][ny] == 1) dist[nx][ny] = dist[current.x][current.y];
                    else dist[nx][ny] = dist[current.x][current.y] + 1;
                    q.offer(new Node(nx, ny));
                }
            }
        }
    }
    
    public static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}