백준 2665 '미로만들기'

Bonwoong Ku·2023년 9월 12일

알고리즘 문제풀이

목록 보기

28/110

아이디어

이웃은 4방 탐색
이웃이 검은 방이면 깊이가 1 증가한다.
PQ를 사용한 다익스트라

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int n;
	static boolean[][] map;	// 1: 흰 방, 2: 검은 방
	static boolean[][] enqueued;
	static PriorityQueue<Data> pq = new PriorityQueue<>();	
	
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, 1, 0, -1};
	
	public static void main(String[] args) throws Exception {
		n = Integer.parseInt(rd.readLine());
		
		map = new boolean[n][n];
		for (int y=0; y<n; y++) {
			char[] in = rd.readLine().toCharArray();
			for (int x=0; x<n; x++) {
				map[y][x] = in[x] == '1';
			}
		}
		enqueued = new boolean[n][n];

		pq.add(new Data(0, 0, map[0][0] ? 0 : 1));
		enqueued[0][0] = true;
		while (true) {
			Data data = pq.poll();
			int y = data.y;
			int x = data.x;
			int d = data.d;
			if (y == n-1 && x == n-1) {
				System.out.println(d);
				return;
			}
			for (int i=0; i<4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
				if (enqueued[ny][nx]) continue;
				
				pq.offer(new Data(ny, nx, map[ny][nx] ? d : d + 1));
				enqueued[ny][nx] = true;
			}
		}
	}
	
	static class Data implements Comparable<Data>{
		int y, x, d;
		Data(int y, int x, int d) {
			this.y = y;
			this.x = x;
			this.d = d;
		}
		@Override
		public int compareTo(Data o) {
			return Integer.compare(this.d, o.d);
		}
		
	}
}