[Java] Lv.2 프로그래머스 게임 맵 최단거리

설명

전형적인 BFS 문제이다.
잠깐 BFS 말고 다른 알고리즘 공부하니 BFS 가 기억이 잘 안나서 찾아봤다...ㅠㅠ

게임 캐릭터가 상대팀 진영에 최대한 빨리 도착하는 것이 유리 이것을 보고 BFS 로 풀어야겠다고 생각했다.

코드

import java.util.*;
class Solution {
    static int[][] visited;		// 칸 수 저장 배열
    static int[] x = {0, -1, 0, 1};		// 좌, 우
    static int[] y = {1, 0, -1, 0};		// 상, 하
    public int solution(int[][] maps) {
        int answer = 0;
        visited = new int[maps.length][maps[0].length];

        BFS(0, 0, maps);	// 0,0부터 시작.
        answer = visited[maps.length -1][maps[0].length -1];	// visited의 마지막 값을 answer에 담는다.

        if (answer == 0) answer = -1;	// visited 에 값이 없었다면 갈 수 없는 게임

        return answer;
    }
    public static void BFS(int i, int j, int[][] maps) {
        Queue<int[]> q = new LinkedList<>();	// 큐를 배열 타입으로 선언
        visited[i][j] = 1;		// 1부터 시작
        q.add(new int[]{i, j});

        while (!q.isEmpty()) {		// 큐에 값이 없을때까지
            int[] now = q.remove();
            int dx = now[0];
            int dy = now[1];

            for (int a = 0; a < 4; a++) {
                int nowx = dx + x[a];
                int nowy = dy + y[a];
                if (nowx < 0 || nowx > maps.length -1 || nowy < 0 || nowy > maps[0].length -1) continue;
                // 좌표 값이 0보다 작거나 maps 의 크기 보다 큰지 확인
                if (visited[nowx][nowy] == 0 && maps[nowx][nowy] == 1) {	
                // 방문하지 않은 배열이면서 갈 수 있는 길일 때
                    visited[nowx][nowy] = visited[dx][dy] + 1;
                    q.add(new int[]{nowx, nowy});
                }
            }
        }
    }
}