[백준] 1261. 알고스팟 (Java)

문제

1261번: 알고스팟

 

알고리즘

0-1 너비우선탐색 (0-1 BFS)

 

풀이

벽이 없다면 가중치가 0이고, 벽이 있다면 가중치가 1인 0-1 BFS 문제이다.

가중치가 동일하지 않기 때문에 큐를 사용하면 N,M에 도착했을 때의 벽을 부순 횟수가 최솟값이라고 확신할 수 없다.

 

따라서 큐가 아닌 우선순위 큐를 이용하여 부순 횟수가 적은 순으로 정렬하고 탐색해 N, M에 도착했을 때 벽을 부순 횟수가 최솟값이 될 수 있도록 한다.

 

* 우선순위 큐에서 꺼낼 때 N,M 인지 검사하지 않고, 우선순위 큐에 삽입할 때 검사하면 다음 테스트 케이스에서 틀리게 된다.

1 1
0

 

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		int[] dy = { -1, 1, 0, 0 };
		int[] dx = { 0, 0, -1, 1 };

		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());

		int[][] board = new int[N + 1][M + 1];
		boolean[][] visited = new boolean[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			String str = br.readLine();
			for (int j = 1; j <= M; j++) {
				board[i][j] = str.charAt(j - 1) - '0';
			}
		}

		PriorityQueue<Pos> pq = new PriorityQueue<>();
		pq.add(new Pos(1, 1, 0));
		visited[1][1] = true;

		while (!pq.isEmpty()) {
			Pos cur = pq.poll();

			if (cur.y == N && cur.x == M) {
				System.out.println(cur.t);
				break;
			}

			for (int d = 0; d < dy.length; d++) {
				int ny = cur.y + dy[d];
				int nx = cur.x + dx[d];

				if (ny < 1 || ny > N || nx < 1 || nx > M || visited[ny][nx]) continue;

				visited[ny][nx] = true;
				pq.add(new Pos(ny, nx, cur.t + board[ny][nx]));
			}
		}
	}

	static class Pos implements Comparable<Pos> {
		int y, x, t;

		public Pos(int y, int x, int t) {
			this.y = y;
			this.x = x;
			this.t = t;
		}

		@Override
		public int compareTo(Pos o) {
			return t - o.t;
		}
	}
}