[백준 / BOJ] 1261번 : 알고스팟 - JAVA

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

우선순위 큐를 이용한 BFS

벽을 최소한으로 부숴야 하기 때문에 BFS를 선택했다. 단, 그냥 큐를 사용해서 풀 경우에는 움직인 거리 기준으로 큐에 들어가기 때문에, 우선순위 큐를 사용하여 벽을 부순 횟수를 기준으로 정렬되도록 했다.

 

처음에는 방문 체크 배열 v를 int 배열로 만들어 어떤 위치에 도달했을 때, 그 때까지 부순 벽의 개수를 저장하려 했는데, 어차피 벽을 부순 횟수 기준으로 poll되기 때문에 boolean으로 방문 체크만 해도 된다는 것을 깨달았다. 어떤 곳에 처음으로 방문한다면 현재 내가 벽을 부순 횟수가 도착할 때까지 최소로 부순 횟수인 것이다. 

 

전체 코드

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		char[][] wall = new char[N][M];
		boolean[][] v = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			wall[i] = br.readLine().toCharArray();
		}
		
		PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
		});
		
		que.offer(new int[] {0, 0, 1});
		v[0][0] = true;
		
		int[] dr = {-1,0,1,0};
		int[] dc = {0,-1,0,1};
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			if(cur[0] == N - 1 && cur[1] == M - 1) {
				System.out.println(cur[2] - 1);
				return;
			}
			
			for (int d = 0; d < 4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(nr >= N || nc >= M || nr < 0 || nc < 0) continue;
				if(v[nr][nc]) continue;
				if(wall[nr][nc] == '1') {
					v[nr][nc] = true;
					que.offer(new int[] {nr, nc, cur[2] + 1});
				} else {
					v[nr][nc] = true;
					que.offer(new int[] {nr, nc, cur[2]});
				}
			}
		}
		
	}

}