[BFS] 백준 2178번 미로 탐색 [Java]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] iparr = br.readLine().split(" ");
		int n = Integer.parseInt(iparr[0]);
		int m = Integer.parseInt(iparr[1]);
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		Map<int[], Integer> distance = new HashMap<>();
		
		boolean[][] visit = new boolean[n][m];
		int[][] map = new int[n][m];
		
		for (int i = 0; i < n; i++) {
			map[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
		}
		
		int x = 0;
		int y = 0;
		Queue<int[]> que = new LinkedList<>();
		int[] target = new int[] {x, y}; 
		que.add(target);
		visit[x][y] = true;
		distance.put(target, 1);
		
		while(!que.isEmpty()) {
			int[] np = que.poll();
			int nx = np[0];
			int ny = np[1];
			
			if (nx == n - 1 && ny == m - 1) {
				target = np;
				break;
			}
			
			for (int i = 0; i < dx.length; i++) {
				int[] pp = {nx + dx[i], ny + dy[i]};
				int px = pp[0];
				int py = pp[1];
				
				if(px < 0 || px > n - 1 || py < 0 || py > m - 1) {
					continue;
				}
				
				if(!visit[px][py]) {
					visit[px][py] = true;
					if(map[px][py] == 1) {
						que.add(pp);
						
						if(distance.get(pp) == null) {
							distance.put(pp, distance.get(np) + 1);
						} else {
							distance.put(pp, Math.min(distance.get(pp), distance.get(np) + 1));
						}
					}
				}
				
			}
		}
		
		System.out.println(distance.get(target));
		
	}
}

 

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

 

기초적인 BFS문제로

키 포인트는 좌표 별 최소 거리값을 저장하는 것이다.

 

내 경우에는 int 배열을 키로 하고 int 값을 갖고 있는 HashMap에 distance 인스턴스에

키: x, y 좌표의 배열 형태

값: 해당 좌표의 최소 거리

형태로 저장해 관리했다.