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

📙 1. 문제

Link : https://school.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) 위치에 있습니다.

 

풀이 1 : DFS (시간초과)

function solution(maps) {
    let answer = Infinity;
    const [ySize,xSize] = [maps.length,maps[0].length]
    
    const direction = [
        [0,1],
        [1,0],
        [0,-1],
        [-1,0],
    ];
    const dfs = (y,x,cnt) => {
        if(y===ySize-1 && x===xSize-1){
            answer = Math.min(answer,cnt)
            return;
        }
        for(let i=0;i<4;i++){
            let [goY,goX]=[y+direction[i][0],x+direction[i][1]]
            if(goY<0 || goY>=ySize || goX<0 || goX>=xSize || !maps[goY][goX]) continue;
            maps[goY][goX]=0
            dfs(goY,goX,cnt+1);
            maps[goY][goX]=1
        }
    }
    maps[0][0]=0;
    dfs(0,0,0);
    return answer === Infinity?-1:answer+1
}

 

정확성 테스트는 모두 통과하였다. 하지만 DFS는, 다른 경우에서 먼저 목적지에 도착해도 모든 경우의 수를 탐색하기 때문에 시간초과로 인해 효율성 테스트를 통과하지 못했다.

 

 풀이 2 : BFS (성공)

function solution(maps) {
    let answer = Infinity;
    const [ySize,xSize] = [maps.length,maps[0].length]
    
    const direction = [
        [0,1],
        [1,0],
        [0,-1],
        [-1,0],
    ];
    const queue = [];
    queue.push([0,0,0]);
    maps[0][0] = 0;
    while(queue.length>0){
        let [y,x,cnt] = queue.shift();
        if(y===ySize-1 && x===xSize-1) {
            answer=Math.min(cnt,answer)
            break;
        }
        for(let i=0;i<4;i++){
            let [goY,goX]=[y+direction[i][0],x+direction[i][1]]
            if(goY<0 || goY>=ySize || goX<0 || goX>=xSize || !maps[goY][goX]) continue;
            maps[goY][goX]=0
            queue.push([goY,goX,cnt+1])
        }
    }
    return maps[ySize-1][xSize-1]===1?-1:answer+1
}

• queue에 [y,x,cnt]를 push 하며 탐색하였다.
• 방문할 노드는 queue에 push 하고, 방문하였다면 shift 하는 방식이다.
• 방문하려는 노드가 maps범위를 벗어나거나, 값이 0이라면(즉, 벽이거나 이미 방문한 노드) continue로 queue에 push 하지 않는다.
• queue에 push 하며 해당 노드는 0으로 값을 변경하여 지나왔음을 표시한다. -> visited배열을 따로 관리할 필요가 없다.

---

🤔 2. 느낀 점

과거에는 'maps.length'를 직접 사용하여 하드코딩했었지만, 이번에는 ySize와 xSize와 같이 미리 변수 화하여 사용하였다. 이렇게 하니 코드가 더 직관적이고 간결해지며, 실수가 줄어든 것을 느낄 수 있었다. ySize와 xSize 변수를 알맞게 설정하면, "여기서 문제가 있을까?" 걱정을 하지 않아도 되어 자연스럽게 실수가 줄어들고 시간도 절약된다.
비슷한 BFS 문제를 약 1년 전에도 많이 풀어보았다. 그때와 비교해 이번에 작성한 BFS 코드가 훨씬 깔끔해진 것을 확인할 수 있다. 다양한 알고리즘 문제를 풀어보며 실력이 분명히 향상되어 뿌듯한 기분이 든다.

 

🤩 3. 한 번 더 짚고 갈 점

DFS와 BFS는 같은 탐색 방법이 절대 아니다. 고로 소요되는 시간 또한 다르다. 그러한 점을 고려하여 앞으로는 문제 특성에 맞게 DFS를 사용할지, BFS를 사용할 지 결정하도록 하자.

BFS와 DBS 사용하는 경우

참고

1) 그래프의 모든 정점을 방문해야 하는 문제 : DFS, BFS 뭐든 상관없다. 편한 걸 쓰면 된다.
2) 경로의 특징을 저장하는 문제 : 예시로 각 정점에 숫자가 있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제. 각각의 경로마다 그 특징을 저장해두어야 하는 문제는 DFS를 사용한다.
3) 최단거리를 구하는 문제 : 미로 찾기 등 최단거리를 구하는 경우 BFS가 좋다. DFS로 경로를 탐색하면 처음 발견하는 해답이 최단거리가 아닐 수도 있지만 BFS는 현재노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리다.
4) 검색대상그래프가 많이 클 때 DFS가 좋다고 한다.
5) 검색대상의 규모가 별로 크지 않고 검색시작지점으로부터 원하는 대상이 별로 멀지 않으면 BFS.

 

위 문제의 경우 3번에 해당하여, BFS가 적합하다.