-
[CodeKata] 프로그래머스 : 7.3(토), 합승 택시 요금Algorithm 2021. 7. 4. 21:48반응형
🥋 Oooth More!! (Level 3)
🧮 풀이
각 경로별로 최단비용을 계산하는 플로이드-와샬 알고리즘을 기반으로 푸는 문제임을 인지했다.
하지만, 구체적인 풀이를 구현하지 못해 모범답안을 분석하였다.
🖇 리뷰
function solution (n, s, a, b, fares) { const board = new Array(n).fill().map(_ => new Array(n).fill(Infinity)); for(let i = 0; i < n; i++) board[i][i] = 0; fares.forEach(pos => { const [x, y, weight] = pos; board[x-1][y-1] = weight; board[y-1][x-1] = weight; }); for(let k = 0; k < n; k++) { for(let i = 0; i < n; i++) { for(let j = 0; j < n; j++) { if(board[i][j] > board[i][k] + board[k][j]) board[i][j] = board[i][k] + board[k][j]; } } } let answer = board[s-1][a-1] + board[s-1][b-1]; for(let i = 0; i < n; i++) { const shortest = board[s-1][i] + board[i][a-1] + board[i][b-1]; answer = Math.min(answer, shortest); } return answer; }
- 먼저, 그래프를 만들 board를 선언하고, 2차원 배열(n * n)을 할당한다. 가중치 최소값으로 최신화하므로 기본값은 Infinity 다.
- 자기자신(board[i][i])은 0을 넣는다. fares 가중치 값들을 순회하며, board의 각 경로에 가중치값(weight)를 넣어준다.
- 다음 3중 순회문은 각각의 노드별 최소가중치를 계산하는 플로이드-와샬 알고리즘이다. 직접 가는것과 특정 노드(k)를 거쳐가는 것, 둘 중 최소의 값으로 board 가중치들을 최신화해준다.
- 최초로 answer는 두사람이 각각 최소값으로 이동하는 경우이다. board[s][a], board[s][b] 가 여기에 해당된다.
- shortest는 s에서 특정 노드(i)를 거쳐 각 노드(a, b)로 이동하는 최소값이다. 모든 경우를 확인해, 최소값을 answer에 넣는다.
확실히, 카카오에다가 그래프 문제여서 복잡하게 생각을 했지만, 우려했던거보다는 간단하게 풀 수 있는 문제였다.
특히, 고난이도의 문제일수록 단순한 그래프 탐방보다는 경로 + 가중치의 상급문제가 출제되곤 할 것이다. 이 때 플로이드-와샬을 적절하게 적용해야겠다!
반응형'Algorithm' 카테고리의 다른 글
[CodeKata] 프로그래머스 : 7.19(월), 여행경로 / 베스트앨범 (0) 2021.07.20 [CodeKata] 프로그래머스 : 7.10(토), 경주로 건설 (0) 2021.07.10 [CodeKata] 프로그래머스 : 6.19(토), 다단계 칫솔 판매 / 단어 변환 (0) 2021.06.14 [CodeKata] 프로그래머스 : 6.11(금), 보석 쇼핑 / 이중우선순위큐 (0) 2021.06.10 [CodeKata] 프로그래머스 : 6.5(토), 셔틀버스 (0) 2021.06.06