백준_미로만들기_2665

문제 링크

조건

•  n  : 방 크기 n*n, 1~50이하

 

접근 방법

• check[][] : 방문 체크를 위한 int[][] 배열
• check 배열을 사용해 검은 방을 더 적게 들린 경우만 queue에 집어넣어 bfs 탐색

 

솔루션

public class Main_2665_미로만들기 {

	static int N;//방 크기 N*N
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().trim());
		
		boolean[][] map = new boolean[N][N];
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine().trim();
			for(int j = 0; j < N; j++) {//false일 때 검은 방
				map[i][j] = str.charAt(j) == '1' ? true : false;
			}
		}
		
		int[][] check = new int[N][N];
		Queue<int[]> queue = new LinkedList<int[]>();
		
		int[] dr = {0,0,-1,1};
		int[] dc = {1,-1,0,0};
		
		int[] cur = null;
		int r,c,black,nr,nc;
	
		queue.add(new int[] {0,0,0});//{좌표 r, 좌표 c, 검은 방 개수}
		for(int i = 0; i < N; i++) Arrays.fill(check[i], Integer.MAX_VALUE);
		check[0][0] = 0;
		
		int min = Integer.MAX_VALUE;
		while(!queue.isEmpty()) {
			cur = queue.poll();
			r = cur[0];
			c = cur[1];
			black = cur[2];
			
			if(r == N-1 && c == N-1) {//도착
				if(min > black) min = black;
				continue;
			}
			
			for(int j = 0; j < 4; j++) {
				nr = r + dr[j];
				nc = c + dc[j];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
				
				if(map[nr][nc]) {//흰 방일 경우
					if(check[nr][nc] > black) {
						check[nr][nc] = black;
						queue.add(new int[] {nr,nc,black});
					}
				}else {//검은 방일 경우
					if(check[nr][nc] > black+1) {
						check[nr][nc] = black+1;
						queue.add(new int[] {nr,nc,black + 1});
					}
				}
			}
			
		}
		System.out.println(min);
			
		
	}
	
}

 

리뷰

• 방문 체크 시 들렸던 검은 방 개수를 비교하기 위해 int[][]배열을 활용하는 게 포인트인듯..
• boolean[n*n][n][n] 형태로 3차원 boolean 배열을 사용해 방문 체크 하는 방법도 있음!