728x90
반응형
코딩테스트 연습 - 배달
5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4
programmers.co.kr
문제
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이
문제를 보면 딱 보아도 최단거리 그래프 문제입니다.
최단거리 알고리즘으로는 다익스트라와 플로이드-와샬이 있지만,
출발점이 정해져 있는 상황이라면 다익스트라를 사용하는 것이 좋습니다.🤗
해당 문제는 1번 마을이 출발점으로 고정되어 있으므로 다익스트라 알고리즘을 사용하여
최단거리가 K 이하인 마을의 개수를 계산해주면 됩니다.
알고가자
Kotlin으로 코딩테스트를 푼지 얼마 되지 않아, 문제를 풀 때 사용한 kotlin 문법에 대해서 잠시 정리해보겠습니다.😪
- 2차원 배열 만들기
val maps = Array(N, { IntArray(N, {0}) })
- 우선순위 큐
Pair를 이용한 우선순위 큐 만들기
val queue = PriorityQueue(Comparator<Pair<Int, Int>>{ a, b ->
// 비교 코드
return a.second - b.second
})
문제 풀이 시, 주의할 점
문제를 다 풀고 다시 테스트 케이스 채점을 해보니, 몇 개 틀린 문제들이 있었습니다.
왜틀??🤔
다시 한번 문제를 읽어보니, 1번 마을에서부터 시작해서 다시 1번 마을로 돌아오는 경로를
잘못 계산하고 있었습니다.
1번 마을은 무조건 0시간 이라는 것에 유의해주세요.
코드
import java.util.*
class Solution {
fun solution(N: Int, road: Array<IntArray>, k: Int): Int {
var answer = 0
val INF = (1e9).toInt()
// 각 정점까지의 최단거리를 저장할 배열
val dp = IntArray(N){ INF }
// 마을간의 연결관계
val maps = Array(N, { IntArray(N, {INF})})
road.forEach{ (a,b,c) ->
if (maps[a-1][b-1] > c) {
maps[a-1][b-1] = c
maps[b-1][a-1] = c
}
}
val q = PriorityQueue(Comparator<Pair<Int, Int>>{a, b -> a.second - b.second})
q.add(Pair(0,0))
while(q.isNotEmpty()) {
val (s, cost) = q.poll()
for ((e,c) in maps[s].withIndex()) {
if (c != INF) {
val nc = cost + c
if (dp[e] > nc) {
dp[e] = nc
q.add(Pair(e,nc))
}
}
}
}
return dp.filterIndexed{ i,x -> if (i==0) true else x<=k}.size
}
}
반응형
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스] Lv 2. 모음사전 (0) | 2022.05.25 |
---|---|
[프로그래머스] Lv 2. 전력망을 둘로 나누기 (0) | 2022.05.25 |
[프로그래머스] Lv 2. 2개 이하로 다른 비트 (0) | 2022.05.13 |
[프로그래머스] Lv 2. 괄호 회전하기 (0) | 2022.05.13 |
[프로그래머스] Lv 2. 피로도 (0) | 2022.05.13 |