[BOJ 2665] 미로만들기 (Java)

BOJ 2665 미로만들기

문제풀이

단순한 BFS인데도 불구하고 굉장히 고민했다... 이 문제는 구불구불하게 갈 수 있다. 즉 최단거리가 아니라 최소로 검은 방을 없애고 가는 것이기 때문에 많은 방을 들리는 것은 상관없다. 따라서

• 왼쪽 위에서 오른쪽 아래로 갱신해가는 DP는 불가하다.
• 단순한 방문체크를 통한 BFS는 불가하다.

특정 방에 도착했을 때 이 방에 도착하는 여러가지 경우 중에 거쳐온 검은 방의 갯수가 가장 적은 방법을 택한다. 즉, 방문체크를 int 배열로 만들어 각 방에 도착했을 때 거쳐온 검은 방의 최솟값을 기록한다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	
	static class Node{
		int r, c;
		
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	
	static Queue<Node> q;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int[][] map, visited;
	static int N; 
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		q = new LinkedList<>();
		visited = new int[N][N];
		map = new int[N][N];
		
		for(int i = 0 ; i < N ; ++i) {
			char[] line = br.readLine().toCharArray();
			for(int j = 0 ; j < N ; ++j) {
				map[i][j] = line[j] - '0';
			}
		}

		for(int r = 0 ; r < N ; ++r) {
			Arrays.fill(visited[r], Integer.MAX_VALUE);
		}
		
		q.offer(new Node(0, 0));
		visited[0][0] = 0;
		
		bfs();
		
		System.out.println(visited[N - 1][N - 1]);
	}

	private static void bfs() {
		while(!q.isEmpty()) {
			Node now = q.poll();

			for(int d = 0 ; d < 4 ; ++d) {
				int nr = now.r + dir[d][0];
				int nc = now.c + dir[d][1];
				if(nr >= N || nr < 0 || nc >= N || nc < 0) continue;
				
				// 검은 방
				if(map[nr][nc] == 0) {
					if(visited[nr][nc] > visited[now.r][now.c] + 1) {
						visited[nr][nc] = visited[now.r][now.c] + 1;
						q.offer(new Node(nr, nc));
					}
				} else {
					if(visited[nr][nc] > visited[now.r][now.c]) {
						visited[nr][nc] = visited[now.r][now.c];
						q.offer(new Node(nr, nc));
					}
				}
			}
		}
	}
}