게임 맵 최단거리

import java.util.*;
class Solution {
    private static int[] addRow = { -1, 0, 1, 0 };
    private static int[] addCol = { 0, 1, 0, -1 };
    
    public int solution(int[][] maps) {
        int answer = 0;
        int[][] weight = new int[maps.length][maps[0].length];
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(new Node(0, 0, 1));
 
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int row = node.row;
            int col = node.col;
            
            // 이미 탐색됐거나 벽일 경우
            if (weight[row][col] > 0 || maps[row][col] == 0)
                continue;
            weight[row][col] = node.dis;
            
            for (int i = 0; i < 4; i++) {
                // 좌, 우, 상, 하 탐색
                int nextRow = row + addRow[i];
                int nextCol = col + addCol[i];
                // 범위를 초과했을 경우
                if (nextRow < 0 || nextRow >= maps.length || nextCol < 0 || nextCol >= maps[nextRow].length)
                    continue;
                queue.add(new Node(nextRow, nextCol, node.dis + 1));
            }
        }
        answer = weight[weight.length - 1][weight[0].length - 1];
        if (answer == 0)
            answer = -1;
        return answer;
    }
}
 
class Node {
    int row;
    int col;
    int dis;
 
    public Node(int row, int col, int dis) {
        this.row = row;
        this.col = col;
        this.dis = dis;
    }
}

BFS(너비 우선 탐색)를 이용한 경로 탐색 코드이다.

Queue에 LinkedList를 생성함으로써 여러 값을 동시에 저장하며 순차적으로 조회할 수 있다.

 

기존에는 DFS(깊이 우선 탐색)를 이용한 경로 탐색 코드를 작성했으며 해당 코드는 아래와 같다.

import java.util.*;
class Solution {
        public void Search(int[][] maps, int[][] weight, int i, int j, int value) {
        if (i < 0 || j < 0 || i >= maps.length || j >= maps[0].length) // 범위를 초과했을 경우
            return;
        if (maps[i][j] == 0) // 벽인 경우
            return;
        else if (i == maps.length - 1 && j == maps[0].length - 1) { // 도착한 경우
            if (weight[i][j] > value)
                weight[i][j] = value;
        } else {
            if (weight[i][j] > value)
                weight[i][j] = value;
            else // 다시 한 바퀴 돌았을 경우
                return;
            value++;
            Search(maps, weight, i + 1, j, value);
            Search(maps, weight, i - 1, j, value);
            Search(maps, weight, i, j + 1, value);
            Search(maps, weight, i, j - 1, value);
        }
    }
    public int solution(int[][] maps) {
        int answer = 0;
        int[][] weight = new int[maps.length][maps[0].length];
 
        // 가중치 초기화
        for (int i = 0; i < weight.length; i++)
            Arrays.fill(weight[i], maps.length * maps[0].length + 1);
        
        Search(maps, weight, 0, 0, 1);
        answer = weight[maps.length - 1][maps[0].length - 1];
        if(answer == maps.length * maps[0].length + 1)
            answer = -1;
        return answer;
    }
}

이 코드 또한 정확도는 100%가 나오지만 효율성 테스트에서 50% 맞아 BFS로 수정하였다.