프로그래머스 - 게임 맵 최단거리

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 게임 맵 최단거리

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

풀이 : BFS 알고리즘을 통해 최단 거리를 계산한다.
만일 도착점이 변화 없으면 갈 방법이 없으므로 -1을 리턴, 도착점에 변화가 있으면 해당 지점의 최소값을 리턴한다.

import java.util.*;

class Solution {
    static boolean [][] vst;
	public int solution(int[][] maps) {
		int n = maps.length;
		int m = maps[0].length;
		int [][] arr = new int [n+2][m+2];
		vst = new boolean [n+2][m+2];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				arr[i+1][j+1] = maps[i][j];
			}
		}
		LinkedList<int [] > qu = new LinkedList<int[]>();
		qu.add(new int [] {1, 1, 1});
		vst[1][1] = true;
		go(qu, arr);
		return arr[n][m] == 1 ? -1 : arr[n][m];
    }
    private static void go(LinkedList<int[]> qu, int[][] arr) {
		if(qu.isEmpty()) return;
		int size = qu.size();
		int [] dx = {0, 0, 1, -1};
		int [] dy = {1, -1, 0, 0};
		for (int i = 0; i < size; i++) {
			int [] p = qu.poll();
			for (int j = 0; j < 4; j++) {
				int x = p[1] + dx[j];
				int y = p[0] + dy[j];
				int point = p[2] + 1;
				if(arr[y][x] == 0 || vst[y][x]) continue;
				vst[y][x] = true;
				if(arr[y][x] == 1) arr[y][x] = point;
				else arr[y][x] = Math.min(arr[y][x], point);
				qu.add(new int [] {y, x, point});
			}
		}
		go(qu, arr);
	}
}