[프로그래머스] 게임 맵 최단거리(Java)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

---

문제 풀이

전형적인 BFS 문제 중 하나였다.

 

import java.util.*;

class Solution {
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	static boolean[][] visited;
	static int N;
	static int M;

	public int solution(int[][] maps) {
		N = maps.length;
		M = maps[0].length;
		visited = new boolean[N][M];

		return BFS(0, 0, maps);
	}

	private int BFS(int x, int y, int[][] maps) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {x, y});

		// 시작점 막힌 경우
		if(maps[x][y] == 0) {
			return -1;
		}

		while(!q.isEmpty()) {
			int[] now = q.poll();
			int nowX = now[0];
			int nowY = now[1];
			visited[nowX][nowY] = true;

			for(int i=0; i<4; i++) {
				int nextX = nowX + dx[i];
				int nextY = nowY + dy[i];


				if(nextX>=0 && nextY>=0 && nextX<N && nextY<M) {
					if(!visited[nextX][nextY] && maps[nextX][nextY] != 0) {
						visited[nextX][nextY] = true;
						maps[nextX][nextY] = maps[nowX][nowY] + 1;
						q.offer(new int[] {nextX, nextY});
					}
				}
				if(nextX == N-1 && nextY == M-1) {
					return maps[N-1][M-1];
				}
			}
		}
		return -1;

	}
}