알고스팟


백준 [1261] 알고스팟

문제보기
Alt text

풀이방법

  • BFS

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, ans;
	static int[][] map;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		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][M];
		ans = 987654321;

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

		escape();
		System.out.println(ans);
	}

	public static void escape() {
		int[][] visited = new int[N][M];
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { 0, 0, 0 });
		visited[0][0] = -1;

		while (!queue.isEmpty()) {
			int[] q = queue.poll();

			if (q[0] == N - 1 && q[1] == M - 1) {
				if (visited[N - 1][M - 1] == -1) {
					ans = 0;
				} else {
					ans = Math.min(ans, visited[N - 1][M - 1]);
				}
				continue;
			}

			if (ans <= q[2])
				continue;

			for (int k = 0; k < 4; k++) {
				int x = q[0] + dx[k];
				int y = q[1] + dy[k];

				if (isRange(x, y)) {
					if (map[x][y] == 0) {
						if (visited[x][y] == 0 || visited[x][y] > q[2]) {
							if (q[2] == 0)
								visited[x][y] = -1;
							else
								visited[x][y] = q[2];
							queue.add(new int[] { x, y, q[2] });
						}
					} else {
						if (visited[x][y] == 0 || visited[x][y] > q[2] + 1) {
							visited[x][y] = q[2] + 1;
							queue.add(new int[] { x, y, q[2] + 1 });
						}
					}
				}
			}
		}
	}

	public static boolean isRange(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < M;
	}
}