-
[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; }
- result는 누적계산 횟수이자, 곧 우리가 구하고자하는 최단거리의 값이 될 것이다.
- queue는 현재 방문한 노드들이 저장되어있다. 이 노드를 통해 다음 노드의 방문여부를 결정한다.
- visited는 maps와 크기가 똑같은 이차원 배열이며, 안에는 false 값들로 채워져있다. 노드를 방문하면 이를 true로 바꿔준다.
- while 반복문을 돌린다. (조건은 queue 가 존재하는 동안) 큐가 존재한다는 것은 노드를 방문했다는 의미로, result에 1을 더한다.
- 현재 노드들(queue)을 shift() 한 뒤, 다음 노드를 확인한다. 이미 방문했다면 continue, 아니라면 maps와 visited를 막는다.
- 현재 노드좌표(curY, curX)가 size-1과 같다면 끝에 도달한 것이므로, result 값을 반환하는 시점인 것이다.
- 아니라면, 상하좌우 4개 좌표에 대해 size-1을 초과하지 않고, maps가 1이라면(벽이 아님) queue에 push() 하여 다음 반복문을 준비한다.
- 만약, 반복문 내의 return이 발생하지 않고 queue가 비어서 종료되는 경우가 있을 것이다. 이는 더 이상 이동할 방법이 없다는 의미로, -1을 반환시켜주는 조건이 될 것이다.
DFS, BFS의 적용 경우에 대해서는 어느정도 이해하고 있다. (DFS는 모든 노드를 탐색해야하는 경우의 수, BFS는 최단경로 및 연결조합 등)
추후, 이러한 탐색 알고리즘을 쓰는 문제에 대해서는 스스로 코드구현할 수 있도록 도전해보아야겠다.
* BFS 개념은 지난 DFS 문제에서 함꼐 정리한 내용을 참고해달라. (포스팅(프로그래머스, 타겟 넘버) : abangpa1ace.tistory.com/109)
반응형'Algorithm' 카테고리의 다른 글
[CodeKata] 프로그래머스 : 3.9(화), 숫자의 표현 (0) 2021.03.09 [CodeKata] 프로그래머스 : 3.8(월), 방문 길이 (0) 2021.03.08 [CodeKata] 프로그래머스 : 3.4(목), 다음 큰 숫자 (0) 2021.03.04 [CodeKata] 프로그래머스 : 3.3(수), 올바른 괄호 & 튜플 (0) 2021.03.03 [CodeKata] 프로그래머스 : 3.2(화), 가장 큰 정사각형 찾기 (0) 2021.03.02