[프로그래머스/JavaScript] 게임 맵 최단거리 (Level 2) -BFS

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

코딩테스트 연습 - 게임 맵 최단거리

 

1. 문제 설명

• 위 링크 참고

---

2. 문제 파악

• 시작점에서 목적지까지 최단 거리를 구하는 문제
• 너비 우선 탐색(Breadth First Search, BFS)의 전형적인 문제

---

3. 코드

- 문제 해결을 하지 못하여 다른 사람의 풀이를 분석하려고 한다.

 

1) 변수 설정

• 남동북서를 기준으로 x좌표는 우측, y좌표는 하단으로 이동할 경우를 가정하여 1로 표시. (반대는 -1)
• 맵의 최대길이를 구한다. (맵을 넘어가면 안되기 때문)
  
  

2) 방문 횟수 목록

• 이동한 거리를 관리하는 리스트
• 초기값을 1로 설정하고 목적지의 값이 1이면 도달하지 못한다고 판단
• 해당칸에 이동한 경우 값을 1 증가시킨다.
  

 

3) 시작점 설정

 

4) BFS 시작

 

5) 이동할 수 있는 네 방향을 체크하기 위해 4번 루프를 돌린다.

• 방향마다 이동하게 될 경우의 x, y 값을 구한다. (nx, ny)

 

6 ) 이동하게 될 x, y 값이 0보다 커야하고 맵 보다는 작아야 한다.

• 이동하게 될 x, y 값
  • 1은 해당 위치로 이동
  • 0은 유지
  • -1은 되돌아가는 경우

 

7) 해당 위치의 맵이 이동할 수 있는 상황이고 해당 위치를 처음 방문한 경우

• 이동한 위치에 이동거리 1추가
• queue에 이동한 위치 추가

 

8) 목적지 위치 값이 1이면 도달할 수 없는 위치로 판단하여 -1 값을 return

function solution(maps) {
    // 1.
    const dy = [1,0,-1,0];
    const dx = [0,1,0,-1];
    const row = maps.length;
    const col = maps[0].length;

    // 2.
    const visitCount = [...maps].map((r) => r.map((c) => 1));

    // 3.
    const queue = [[0,0]];  //시작점

    // 4.
    while(queue.length) {
        const [y, x] = queue.shift();

        // 5.
        for(let i = 0; i < 4; i++ ) {
            const ny = y + dy[i];
            const nx = x + dx[i];

            // 6.
            if(ny >= 0 && nx >= 0 && ny < row && nx < col) {
                // 7.
                if(maps[ny][nx] === 1 && visitCount[ny][nx] === 1) {
                    visitCount[ny][nx] = visitCount[y][x] + 1;
                    queue.push([ny,nx]);
                }
            }
        }
    }

    // 8.
    return visitCount[row - 1][col - 1] === 1 ? -1 : visitCount[row - 1][col - 1];    
}

---

4. 결론

• 이 문제를 해결하기 위한 초기 변수 설정에 어떤 것들을 해야할지 판단 필요
• 방문 횟수를 관리하는 목록 필요
• 시작할 위치를 설정(queue)
• 계산식이 어떻게 될지 복잡함에 대한 생각을 버리고 규칙만 정해서 로직 구현
• 이동할 수 있는 조건을 잘 판단하여 queue가 계속 진행 될 수 있도록 구현 필요
• 어렵다