문제

문제 설명

n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

---

Java

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

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

        int n=Integer.parseInt(br.readLine());
        int[][] graph=new int[n][n];
        for(int i=0; i<n; i++){
            String s=br.readLine();
            for(int j=0; j<n; j++)
                graph[i][j]=Character.getNumericValue(s.charAt(j));
        }

        boolean[][] visited=new boolean[n][n];
        //[행, 열, 비용]의 정수 배열을 우선순위큐에 삽입, 정렬 기준:비용
        PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(o->o[2]));
        pq.add(new int[]{0, 0, 0});
        while(!pq.isEmpty()){
            int[] ptr=pq.poll();
            int x=ptr[0];
            int y=ptr[1];
            int cost=ptr[2];

            if(x==n-1 && y==n-1){
                System.out.println(cost);
                return;
            }

            if(visited[x][y])
                continue;
            visited[x][y]=true;

            int[][] directions=new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            for(int[] i:directions) {
                int dx = x + i[0];
                int dy = y + i[1];

                if (dx < 0 || dx >= n || dy < 0 || dy >= n || visited[dx][dy])
                    continue;

                if (graph[dx][dy] == 1)
                    pq.add(new int[]{dx, dy, cost});
                else
                    pq.add(new int[]{dx, dy, cost + 1});
            }
        }
    }
}

---

해결 과정

1. Dijkstra를 사용해서 매번 최소 비용의 노드를 선택해서 목적지를 도달한다. 인접한 방이 흰색이면 같은 비용으로 우선순위큐에 넣고, 검은 방이면 비용+1 해서 우선순위큐에 넣는다.

2. 😁