[백준] 2178 : 미로 탐색 - BFS + Memoization (?)

문제

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

 

 

 

입출력

 

 

---

아이디어

 

예전에는 Queue에 최단 거리를 넣었었는데 

최단 거리를 저장하는 배열을 밖으로 빼보았다 

 

 

코드 

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[][] box;
	static int[][] way = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		box = new int[N][M];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < M; j++) {
				box[i][j] = line.charAt(j) - '0';
			}
		}

		int[][] dp = new int[N][M];
		for (int i = 0; i < N; i++) {
			Arrays.fill(dp[i], Integer.MAX_VALUE);
		}
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { 0, 0 });
		dp[0][0] = 1;
		while (!queue.isEmpty()) {
			int[] now = queue.poll();

			for (int w = 0; w < 4; w++) {
				int nx = now[0] + way[w][0];
				int ny = now[1] + way[w][1];

				if (!inRange(nx, ny))
					continue;
				if (box[nx][ny] == 1 && dp[nx][ny] == Integer.MAX_VALUE) {
					queue.add(new int[] { nx, ny });
					dp[nx][ny] = dp[now[0]][now[1]] + 1;
				}
			}
		}
		System.out.println(dp[N - 1][M - 1]);

	}

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

}