[백준] 2665 미로만들기

문제 출처: https://www.acmicpc.net/problem/2665

2665번: 미로만들기

 

1. 입력

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

: 0은 검은 방, 1은 흰 방을 나타낸다.

 

2. 출력

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

 

3. 풀이

: BFS를 사용해서 풀 수 있다.

: 검은방은 최소로 지나야 하기 때문에 우선순위 큐를 사용해서 현재까지 지난 검은 방의 수가 작은 기준으로 정렬해준다.

 

 

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

public class 미로만들기 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N;
	static int[][] adj;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception{
		N = Integer.parseInt(br.readLine());
		adj = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split("");
			for(int j = 0; j < N; j++) {
				adj[i][j] = Integer.parseInt(tmp[j]);
			}
		}
		bfs();
		System.out.println(min);
	}
	static class Point{
		int r, c, cnt;

		public Point(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
		
	}
	private static void bfs() {
		PriorityQueue<Point> q = new PriorityQueue<>(new Comparator<Point>() {

			@Override
			public int compare(Point o1, Point o2) {
				return o1.cnt - o2.cnt;
			}
			
		});
		boolean[][] v = new boolean[N][N];
		q.offer(new Point(0, 0, 0));
		v[0][0] = true;
		
		while(!q.isEmpty()) {
			Point cur = q.poll();
			
			if(cur.r == N-1 && cur.c == N-1) {
				if(min > cur.cnt ) min = cur.cnt;
				break;
			}

			for(int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				if(nr < 0 || nr >= N || nc < 0 || nc >= N || v[nr][nc])continue;
				if(adj[nr][nc] == 0) q.offer(new Point(nr, nc, cur.cnt+1));
				else q.offer(new Point(nr, nc, cur.cnt));
				v[nr][nc] = true;
			}
		}
	}
}