백준 | 2665번. 미로 만들기 - 다익스트라

⬛ 백준 2665번. 미로 만들기 | 다익스트라

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

2665번: 미로만들기

문제

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

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

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

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

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

---

💚나의 풀이

• 다익스트라로 (0,0) 에서 (N-1, N-1) 좌표까지 one-to-one 이동할 건데
• => 검은 방→ 흰 방 변경을 최소로 하면서 이동 횟수를 구하는 문제이다.
• cost[][] 2차원 가중치 저장용 배열을 생성해둔다.
• → cost[i][j] : i행j열 위치로 최소 변경 횟수에 가는 수
• PQ 에 가중치 적은 값 우선으로 하여 정렬되도록 생성하고
• while문을 돌면서
• 1) 다음이 흰 방 && 기존 cost 값보다 cur[2] 가중치 거쳐 가는 게 적다면 갱신
• 2) 다음이 검은 방 && 기존 cost 값보다 cur[2] +1 가중치 거쳐 가는 게 적다면 갱신
• 마지막에는 cost에 저장된 cost[N-1][N-1] 값 출력하면 된다.

package to_0822_7;

import java.util.*;

/*2655번. 미로 만들기 - 다익스트라 */
public class Main {
	static int N;
	static int[][] cost;
	static int[][] board;
	static PriorityQueue<int[]> pQ;
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		//초기화
		board = new int[N][N];
		cost = new int[N][N];
		//가중치 오름차순 정렬 
		pQ = new PriorityQueue<>((a,b)-> a[2] - b[2]);
		
		//데이터 입력받기 
		for(int i=0; i<N; i++) {
			String tmp = kb.next();
			for(int j=0; j<N; j++) {
				board[i][j] = Character.getNumericValue(tmp.charAt(j));
			}
		}
		
		//이 상태에서 cost max 초기화
		for(int i=0; i<N; i++) Arrays.fill(cost[i], Integer.MAX_VALUE);
		
		//시작값 세팅 
		cost[0][0] = 0;
		pQ.add(new int[] {0, 0, 0});
		
		while(!pQ.isEmpty()) {
			int[] cur = pQ.poll();
			
			//현재 가려고 하는 정점의 가중치가 기존 cost 보다 큰 경우에는 탐색할 필요 X 넘어감 
			if(cost[cur[0]][cur[1]] < cur[2]) continue;
			
			for(int k=0; k<4; k++) {
				int nx = cur[0] + dx[k];
				int ny = cur[1] + dy[k];
				if(nx <0 || ny<0 || nx >=N || ny>= N ) continue;
				
				//똑같이 nx가 흰방 && 이거로 갔을 때 기존 가중치보다 더 작을 경우 갱신
				if(board[nx][ny] == 1 && cost[nx][ny] > cur[2]) {
					cost[nx][ny] = cur[2];
					pQ.offer(new int[] {nx, ny, cur[2]});
				}
				//nx 정점이 검은 방 && 거기로 갔을 때 기존 가중치보다 더 작게 만들 수 있으면 갱신 
				else if(board[nx][ny] == 0 && cost[nx][ny] > cur[2] + 1) {
					cost[nx][ny] = cur[2] + 1;
					pQ.offer(new int[] {nx, ny, cur[2] + 1});
				}
			}
		}		
		//정답은 n-1, n-1에 저장된 cost 가중치 값
		System.out.println(cost[N-1][N-1]);
	}
}