99클럽 코테 스터디 12일차 TIL + BFS(게임 맵 최단거리)

오늘의 과제

프로그래머스 Lv.2에 정렬로 분류된 게임 맵 최단거리입니다.

 

어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.

문제

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

프로그래머스

 

 

먼저 문제 요구사항 요약입니다.

 

0과 1로 이루어진 2차원 배열이 주어집니다.

 

0은 벽이 있어 이동할 수 없는 자리이고, 1은 벽이 없어 이동할 수 있는 자리입니다.

 

게임 캐릭터의 시작점은 (0, 0) 고정이고, 도착지 또한 (n, m) 고정입니다.

 

이동할 수 있는 1을 따라 (n, m)에 도착하는 최단거리를 구하면 됩니다.

 

이 문제는 BFS 기초로 보여지는 문제이며 Queue를 이용하여 풀어나가면 됩니다.

 

이전 DFS는 "깊이" 우선 탐색이었지만, BFS는 "너비"우선 탐색이라는 것에 집중하면 됩니다.

 

깊이는 일단 갈 수 있는 끝까지 가보는 방법이었다면

너비는 현재 노드에서 갈 수 있는 모든 곳을 먼저 방문해보는 방법입니다.

 

문제 조건에 보면 캐릭터는 동,서,남,북 한 칸씩 이동할 수 있으며,

맵을 벗어난 곳으로는 이동할 수 없다고 적혀있습니다.

 

즉, 그림 예시로 보면 캐릭터는 다음과 같이 움직일 수 있습니다.

 

이전 DFS에서 사용했듯 visited 배열을 통해 이전 방문은 들어가지 않는다고 가정했을 때

정중앙을 제외하면 이동할 수 있는 곳은 한 방향 뿐이니 정 가운데 격자를 봐주시면 됩니다.

 

저희는 최단 거리를 구해야 하는데 눈 대중으로 봐도 위쪽 길보다는 오른쪽 길이 더 빠르겠죠?

 

하지만 BFS는 갈 수 있는 모든 곳을 Queue에 담고 일단 이동하기 때문에 목적지에 갈 수 있는

루트는 두 군데가 나옵니다.

 

따라서 더 짧은 값을 기록할 수 있는 전역 변수를 선언해 비교해나가야 합니다.

 

일반적인 탐색의 기본은 아래 틀로 시작되는 것 같습니다.

 

1. 방문체크

2. 이동 가능 루트 체크 (동,서,남,북)

3. 배열 범위체크

 

위 틀에서 추가 요구사항인 목적지에 도착했는지, 몇 칸이나 움직였는지?에 대한

확인 로직만 추가해주면 됩니다.

 

코드 내 주석을 보며 이해하면 더 쉽게 이해하실 수 있습니다.

import java.util.*;

class Solution {
    // 골인하지 못한다면 answer는 MAX_VALUE로 남아있다.
    static int answer = Integer.MAX_VALUE;
    // 캐릭터는 동,서,남,북으로만 이동할 수 있다.
    static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    // 방문 기록
    static boolean[][] visited;
    
    public int solution(int[][] maps) {
        visited = new boolean[maps.length][maps[0].length];
        
        BFS(maps);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    public static void BFS(int[][] maps) {
        Queue<Integer> queue = new LinkedList<>();
        // 캐릭터는 무조건 (0, 0)에서 출발한다.
        visited[0][0] = true;
        queue.add(0);
        queue.add(0);

        while (!queue.isEmpty()) {
            int x = queue.poll();
            int y = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];

                // 맵의 범위를 벗어나지 않는지 체크한다.
                if (nx >= 0 && ny >= 0 && nx < maps.length && ny < maps[0].length) {
                    // 다음 좌표가 목적지라면 이전 기록과 현재 기록을 비교하여 갱신한다.
                    if (nx == maps.length - 1 && ny == maps[0].length - 1) {
                        answer = Math.min(maps[x][y] + 1, answer);
                        return;
                    }
                    // 이동할 곳이 벽이 없는 곳이고(1), 방문하지 않았다면 방문한다.
                    if (maps[nx][ny] == 1 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.add(nx);
                        queue.add(ny);
                        // 이동한 거리를 좌표에 체크해둔다.
                        maps[nx][ny] = maps[x][y] + 1;
                    }
                }
            }
        }
    }
}

 

배운 점

 

아는 패턴이라 싱글벙글 풀었습니다.

 

굉장히 초보적인 문제겠지만 역시 푸는 방법을 아니 생각보다 재밌게 시간을 보냈습니다.

 

지금의 문제는 대놓고 BFS를 사용해라 라고 알려줬지만

사실 조금만 난이도가 올라가도 어떤 풀이 방법을 적용해야 하는지 고민하는게 굉장히 어렵습니다.

 

따라서 지금부터라도 문제를 꼼꼼히 읽으며 알고 있는 풀이 방법을 적용할 수 있는

키포인트를 식별해 내는 능력을 키워야 할 것 같습니다.

 

 

 

오늘의 한줄평

코테는 알고리즘 능력도 평가하지만 문장속 요구사항을 도출해내는 문해력도 평가한다.