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

문제

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

프로그래머스

 

 

풀이

• N x M의 맵 위에서 (1,1)의 위치에서 (N,M)의 위치까지의 최단거리를 구한다.
• 벽은 0으로 입력되고 움직일 수 있는 길은 1로 입력된다.
• 동서남북으로 한칸씩만 움직일 수 있다.
• 맵 밖으로는 이동할 수 없다.
• 도착할 수 없을 때는 -1을 출력한다.

목표까지 최단거리를 찾는 문제이므로 BFS를 사용해서 풀었다.

먼저 풀이에 필요한 요소가 어떤 것이 있는지 생각해 보았다.

방문한 위치를 표시할 boolean형의 2차원 배열 visited와 한 칸씩 이동하는데 필요한 int형 배열 dx, dy, 그리고 BFS 구현에 필요한 Queue를 만들었다. Queue는 현재 위치와 (1,1) 위치로부터 거리를 담아 int형 배열 타입으로 선언하였다. 그리고 시작점인 (1,1) (배열에서는 0,0)과 첫번째 칸을 의미하는 1을 맨 처음 넣고, visited 배열로 방문 처리 해주었다.

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {0, 0, 1});
visited[0][0] = true;

 

 

Queue가 비어있는지 계속 체크하며 순서대로 poll()하며 탐색하였다.

while(!queue.isEmpty()){
	int[] now = queue.poll();
    // now[0]: x 좌표, now[1]: y 좌표, now[2]: 이동거리
}

 

 

이때 좌표가 (N,M)의 위치라면 목표에 도달한 것이기 때문에 조건문을 사용하여 반복문 탈출 조건으로 만들어 준다.

if(now[0] == (n-1) && now[1] == (m-1)){
    return now[2];
}

 

 

다음 칸으로 이동하기 위한 사방 탐색을 실시한다. for문과 dx, dy 배열을 사용해 다음 좌표로 이동한다.

for(int d = 0; d < 4; d++){
    int nx = now[0] + dx[d];
    int ny = now[1] + dy[d];
    
}

 

 

이때 다음 좌표로 이동할 수 있는 조건은 다음과 같다.

• 맵 밖으로 이동하지 않을 것
• 벽이 아닐 것
• 이미 방문한 곳이 아닐 것

위 조건을 만족하는 조건문을 구현하면 다음과 같다.

if(nx < 0 || ny < 0 || nx >= n || ny >= m){
	continue;
}

if(maps[nx][ny] == 0 || visited[nx][ny]){
	continue;
}

 

 

모든 조건을 만족하였다면 칸을 이동하고, 이동한 위치와 거리를 Queue에 넣은 다음 방문하였다고 체크한다.

queue.offer(new int[] {nx, ny, now[2] + 1});
visited[nx][ny] = true;

 

 

더 이상 이동할 곳이 없을 때, 즉 Queue가 텅 빈 경우는 (N,M) 위치에 끝까지 도달할 수 없는 경우이다. 이때는 return -1을 해주며 함수를 종료한다.

 

 

첫번째 예제로 맵 전체의 최단거리를 계산한 결과 다음과 같다.

 

한칸씩 순서대로 이동하며, 이미 방문한 곳은 다시 방문하지 않기 때문에 최단거리를 계산할 수 있는 것이다.

 

 

전체 코드 (Java)

import java.util.*;

class Solution {
    int n;
    int m;
    int[] dx = {0,1,0,-1};
    int[] dy = {1,0,-1,0};
    // int[][] draw;

    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        boolean[][] visited = new boolean[n][m];
        // draw = new int[n][m];

        int answer = bfs(maps, visited);

        // for(int i = 0; i < n; i++){
        //     for(int j = 0; j < m; j++){
        //         System.out.printf("%3d", draw[i][j]);
        //     }
        //     System.out.println();
        // }

        return answer;
    }

    public int bfs(int[][] maps, boolean[][] visited){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {0, 0, 1});
        visited[0][0] = true;

        while(!queue.isEmpty()){
            int[] now = queue.poll();
            // draw[now[0]][now[1]] = now[2];

            if(now[0] == (n-1) && now[1] == (m-1)){
            	return now[2];
            }

            for(int d = 0; d < 4; d++){
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];

                if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                	continue;
                }

                if(maps[nx][ny] == 0 || visited[nx][ny]){
                	continue;
                }

                queue.offer(new int[] {nx, ny, now[2] + 1});
                visited[nx][ny] = true;

            }
        }

        return -1;
    }
}

 

 

후기

BFS로 풀기 좋은 가장 쉬운 문제였다고 생각한다. 좀 더 빨리 풀 수 있도록 연습해야겠다.