백준 2665 - 미로만들기

[문제 바로가기]

 

1. 유형

BFS

 

2. 문제 풀이

2-1. 해설

BFS에서 파생된 문제 중 하나인 벽 뚫기 문제입니다.

만약 이 문제를 DFS 그냥 정말 탐색하게 된다면 시간 초과가 날 것입니다. 따라서 이 문제는 우선순위 큐를 사용한 BFS로 풀어야 합니다.

 

벽을 몇 번 뚫을지 딱 정해주지 않았습니다. 그래서 만나는 벽을 모두 큐에 넣어주면서 탐색해 줘야 합니다. 

우선순위 큐의 정렬 기준은 적게 벽을 통과한 횟수입니다. 벽을 뚫지 않은 길을 먼저 탐색하는 거죠.

 

마지막 좌표에 도달했으면 벽을 파괴한 횟수 출력.

 

끝!

 

핵심코드.

		Queue<int[]> pq = new PriorityQueue<>((a,b) ->{return a[2]-b[2];});

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {
	static int D[][]= {{-1,0},{0,1},{1,0},{0,-1}};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N  =stoi(st.nextToken());
		int grid[][] = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String s = st.nextToken();
			for(int j=0; j<N; j++) {
				grid[i][j] = s.charAt(j)-'0';
			}
		}
		boolean v[][] = new boolean[N][N];
		Queue<int[]> pq = new PriorityQueue<>((a,b) ->{return a[2]-b[2];});
		pq.add(new int[] {0, 0, 0});
		int answer = 0;
		while(!pq.isEmpty()) {
			int cur[] = pq.poll();
			if(cur[0] == N-1 && cur[1]== N-1) {
				answer = cur[2];
				break;
			}
			for(int k=0; k<4; k++) {
				int nr = cur[0] + D[k][0];
				int nc = cur[1] + D[k][1];
				if(nr<0 || nr >=N || nc<0 || nc>=N|| v[nr][nc]) continue;
				v[nr][nc] = true;
				if(grid[nr][nc]==0) {
					pq.add(new int[] {nr,nc, cur[2]+1});
				}else {
					pq.add(new int[] {nr, nc, cur[2]});
				}
			}
		}
		System.out.println(answer);
	}
	
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}