ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [CodeKata] 프로그래머스 : 3.7(일), 게임 맵 최단거리
    Algorithm 2021. 3. 7. 15:34
    반응형

    🥋 Ooooth!! (Level 2)

     

    🧮 풀이

    최단거리이기에 BFS 문제임은 인지했으며, 모범답안을 통해 Javascript에서 queue를 통한 BFS 구현을 공부했다.

     

    🖇 리뷰

    function solution(maps) {
        let result = 0;
        let ySize = maps.length;
        let xSize = maps[0].length;
    
        let queue = [[0, 0]];
        let visited = Array.from(new Array(ySize), () => new Array(xSize).fill(false));
    
        while (queue.length) {
            result++;
            const size = queue.length;
            for (let i = 0; i < size; i++) {
                const point = queue.shift();
                let curY = point[0];
                let curX = point[1];
    
                if (visited[curY][curX]) continue;
    
                maps[curY][curX] = 0;
                visited[curY][curX] = true;
    
                if (curY === (ySize - 1) && curX === (xSize - 1)) return result;
    
                if (curY < (ySize - 1) && maps[curY + 1][curX] === 1) queue.push([curY + 1, curX])
                if (curX < (xSize - 1) && maps[curY][curX + 1] === 1) queue.push([curY, curX + 1])
                if (curY > 0 && maps[curY - 1][curX] === 1) queue.push([curY - 1, curX])
                if (curX > 0 && maps[curY][curX - 1] === 1) queue.push([curY, curX - 1])
            }
        }
    
        return -1;
    }
    1. result는 누적계산 횟수이자, 곧 우리가 구하고자하는 최단거리의 값이 될 것이다.
    2. queue현재 방문한 노드들이 저장되어있다. 이 노드를 통해 다음 노드의 방문여부를 결정한다.
    3. visitedmaps와 크기가 똑같은 이차원 배열이며, 안에는 false 값들로 채워져있다. 노드를 방문하면 이를 true로 바꿔준다.
    4. while 반복문을 돌린다. (조건은 queue 가 존재하는 동안) 큐가 존재한다는 것은 노드를 방문했다는 의미로, result에 1을 더한다.
    5. 현재 노드들(queue)을 shift() 한 뒤, 다음 노드를 확인한다. 이미 방문했다면 continue, 아니라면 maps와 visited를 막는다.
    6. 현재 노드좌표(curY, curX)가 size-1과 같다면 끝에 도달한 것이므로, result 값을 반환하는 시점인 것이다.
    7. 아니라면, 상하좌우 4개 좌표에 대해 size-1을 초과하지 않고, maps가 1이라면(벽이 아님) queue에 push() 하여 다음 반복문을 준비한다.
    8. 만약, 반복문 내의 return이 발생하지 않고 queue가 비어서 종료되는 경우가 있을 것이다. 이는 더 이상 이동할 방법이 없다는 의미로, -1을 반환시켜주는 조건이 될 것이다.

    DFS, BFS의 적용 경우에 대해서는 어느정도 이해하고 있다. (DFS는 모든 노드를 탐색해야하는 경우의 수, BFS는 최단경로 및 연결조합 등)

    추후, 이러한 탐색 알고리즘을 쓰는 문제에 대해서는 스스로 코드구현할 수 있도록 도전해보아야겠다.

     

    * BFS 개념은 지난 DFS 문제에서 함꼐 정리한 내용을 참고해달라. (포스팅(프로그래머스, 타겟 넘버) : abangpa1ace.tistory.com/109)

     

    반응형
Designed by Tistory.