1261번 : 알고스팟 [Java]

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

1261번: 알고스팟

풀이 방법

벽을 최소한으로 부수고 가는 경우를 찾아야 하기 때문에 우선순위 큐를 통해 벽을 부순 개수에 대해 오름차순으로 사용할 수 있도록 한다.

 

전체 코드

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

public class Main {
	static class Point implements Comparable<Point> {
		int x, y, cnt;

		Point(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
		@Override
		public int compareTo(Point o) {
			return cnt - o.cnt;
		}
	}

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static int N, M;
	static int[][] map;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken()); // 가로
		N = Integer.parseInt(st.nextToken()); // 세로

		map = new int[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			String input = br.readLine();
			for (int j = 1; j <= M; j++) {
				map[i][j] = Character.getNumericValue(input.charAt(j - 1));
			}
		}

		int ans = BFS(1, 1);

		System.out.println(ans);
	}

	public static int BFS(int x, int y) {
		PriorityQueue<Point> q = new PriorityQueue<>();

		q.offer(new Point(x, y, 0));
		boolean[][] visit = new boolean[N + 1][M + 1];
		visit[x][y] = true;

		int dx, dy;
		while (!q.isEmpty()) {
			Point p = q.poll();

			if (p.x == N && p.y == M) {
				return p.cnt;
			}

			for (int i = 0; i < 4; i++) {
				dx = p.x + dr[i];
				dy = p.y + dc[i];

				if (dx < 1 || dy < 1 || dx > N || dy > M) {
					continue;
				}

				if (!visit[dx][dy] && map[dx][dy] == 0) {
					visit[dx][dy] = true;
					q.offer(new Point(dx, dy, p.cnt));
				}

				if (!visit[dx][dy] && map[dx][dy] == 1) {
					visit[dx][dy] = true;
					q.offer(new Point(dx, dy, p.cnt + 1));
				}
			}
		}
		return 0;
	}
}