문제 출처 : [Programmers] 튜플, https://programmers.co.kr/learn/courses/30/lessons/1844

👨‍🏫문제

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

* 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한 사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

예제 입/출력

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

입출력 예에 대한 설명

입출력 예 #1
주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

💻코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
	
    // 전역 정수형 2차원 배열 maps
    static int[][] maps;
    
    public int solution(int[][] m) {
        maps = m;
        
        // 각 칸에 도달하는데 필요한 칸 수를 저장하기 위한 2차원 배열
        int[][] dist = new int[maps.length][maps[0].length];
        Queue<int[]> queue = new LinkedList<>();
        
        queue.offer(new int[] {0, 0});
        dist[0][0] = 1;
        
        /*
         * bfs를 위한 코드
         * 현재 캐릭터 위치를 기준으로 상, 하, 좌, 우로 방향을 나누어서 탐색한다.
         */
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            int y = point[0];
            int x = point[1];
            int[] dy = {-1, 0, 1 ,0};
            int[] dx = {0, 1, 0 , -1};
            
            for(int i = 0; i < 4; i ++){
                int ny = y + dy[i];
                int nx = x + dx[i];
                
                /*
                 * 캐릭터 위치를 기준으로 상, 하, 좌, 우 중 벽이 아니고
                 * 도달한 적이 없으며 맵의 범위를 벗어나지 않는 경우라면
                 * 조건을 만족시키는 칸에 방문, 그리고 해당 칸에 도달하기 위한 칸 수는
                 * 캐릭터가 이동하기 전에 필요했던 칸 수 + 1이 된다.
                 */
                if(isBound(new int[]{ny, nx}) && maps[ny][nx] == 1 && dist[ny][nx] == 0){
                    queue.offer(new int[]{ny, nx});
                    dist[ny][nx] = dist[y][x] + 1;
                }
            }
            
        }
        
        if(dist[maps.length - 1][maps[0].length - 1] == 0){
            return -1;
        }
        
        return dist[maps.length - 1][maps[0].length - 1];
    }
    
    
    // 맵의 범위를 벗어나는지 검사하는 메서드
    static boolean isBound(int[] point){
        int y = point[0];
        int x = point[1];
        
        if(y >= 0 && x >=0 && y < maps.length && x < maps[0].length){
            return true;
        }
        
        return false;
    }
}

💡후기

드디어 DFS, BFS 중에 골라서 쓰는 탐색 문제가 아닌, BFS를 이용해야 풀 수 있는 문제를 만났다. 예~!😆

설명도 꽤 길고 어떻게 구현해야 하나 난해하게 느껴질 수 있지만, Queue를 이용해 BFS를 진행하면 굉장히 쉽게 풀 수 있는 문제였다! 거짓말이 아니고 푸는데 30분도 안 걸린 것 같다...🙄

이 문제처럼 자료구조나 알고리즘 같은 CS 기초를 모르면 하드코딩을 하게 되거나, 효율성이 떨어진다던가 혹은 아예 접근법도 모르는 경우가 생기기도 하니 탄탄한 기초가 중요하다는 것을 한 번 더 깨닫게 되는 문제였다 ㅎㅎ!😊