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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

해당 문제는 가중치가 없는 그래프에서 최단 거리를 구하는 문제이다.

 

가중치가 없는 그래프에서 최단 거리를 구하기 위해선 너비우선탐색(BFS)를 활용할 수 있다.

 

과정은 다음과 같다.

 

1. 

• (0, 0)에서 시작해서 (n-1, m-1)까지의 최단거리를 구해야 한다.

2. 거리를 표시할 해당 맵과 똑같은 크기의 배열을 하나 더 만들어서 출발점을 1, 나머지는 0으로 초기화한다.

 

3. 0,0에서부터 너비우선 탐색을 시작한다. 이때 방문하는 노드의 거리 값은 현재 노드 + 1로 한다.

     결과는 다음과 같다.

 

이제 코드를 보자.

 

3. 내 코드

---

import java.util.*;
class Solution {
    
    private static class Node {
        int r, c;
        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    public int solution(int[][] maps) {
        // 1. 자료구조 초기화
        int[][] distance = new int[maps.length][maps[0].length];
        Queue<Node> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[maps.length][maps[0].length];
        
        distance[0][0] = 1; // 시작점
        queue.add(new Node(0, 0));   
        
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            int row = node.r;
            int col = node.c;
        
            int current_dist = distance[row][col];
            
            
            // 동
            if(col + 1 != maps[0].length && maps[row][col + 1] != 0 && !visited[row][col + 1]) {
                queue.add(new Node(row, col + 1)); // 큐에 추가
                distance[row][col + 1] = current_dist + 1; // 거리 갱신
                visited[row][col + 1] = true; // 방문처리
            }
            // 서
            if(col != 0 && maps[row][col - 1] != 0 && !visited[row][col - 1]) {
                queue.add(new Node(row, col - 1));
                distance[row][col - 1] = current_dist + 1;
                visited[row][col - 1] = true;
            }
            // 남
            if(row + 1 != maps.length && maps[row + 1][col] != 0 && !visited[row + 1][col]) {
                queue.add(new Node(row + 1, col));
                distance[row + 1][col] = current_dist + 1;
                visited[row + 1][col] = true;
            }
            // 북
            if(row != 0 && maps[row - 1][col] != 0 && !visited[row - 1][col]) {
                queue.add(new Node(row - 1, col));
                distance[row - 1][col] = current_dist + 1;
                visited[row - 1][col] = true;
            }
        }
    
    
        return distance[maps.length - 1][maps[0].length - 1] == 0 ? - 1
            :distance[maps.length - 1][maps[0].length - 1];
    }
}

시간 복잡도

• O(N * M)
• N: 맵의 행 M: 맵의 열

 

4. 피드백

---

• 너비우선탐색은 큐에 넣고 바로 방문처리를 해야한다.

// 동
if(col + 1 != maps[0].length && maps[row][col + 1] != 0 && !visited[row][col + 1]) {
    queue.add(new Node(row, col + 1)); // 큐에 추가
    distance[row][col + 1] = current_dist + 1; // 거리 갱신
    visited[row][col + 1] = true; // 방문처리
}