안녕하세요, Kotlin으로 백엔드 개발을 하고 있는 kerry입니다.
지난 포스팅이 이어 다시 한번 oop 스럽게 코테 문제 풀기를 올려볼까합니다.
생각보다 재밌더라구요, 그래서 이번에도 같은 방식으로 풀어볼까 합니다.
문제
등산코스 정하기 - 중급
프로그래머스에서 중급 정도 되는 문제입니다!!
요구사항은 아래와 같습니다.
출입구에서 시작해 산봉우리 하나만 방문한 뒤 다시 출입구로 돌아오는 등산코스를 찾습니다.
각 등산로에는 시간(cost)이 있으며, 해당 코스에서 쉬지 않고 이동한 가장 긴 구간의 시간을 intensity라고 부릅니다.
intensity가 최소가 되도록 등산코스를 정하는 것이 목표입니다.
예시 이미지를 보시죠!!
여기서 파란 색이 출입구, 빨간 색이 산봉우리 입니다.
우선 1번에서 출발해서 5번으로 도착하는 경우를 찾아볼게요!!
1 -> 2 -> 5
1 -> 2 -> 4 -> 5
1 -> 2 -> 4 -> 6 -> 5
이렇게 나오네요, 각 경로 중에서 intensity를 계산해보죠, 경로 중에 있는 가장 cost가 큰 녀석을 고르면 됩니다!
1 -> 2 -> 5 : 4
1 -> 2 -> 4 -> 5 : 3
1 -> 2 -> 4 -> 6 -> 5 : 3
즉, 1번 출입구로 가서, 5번 산봉우리를 가는데 intensity는 3이 나오네요!!
그러면 3번 출입구로 가볼까요?!?!
3 -> 4 -> 5 : 4
3 -> 4 -> 6 -> 5 : 4
3 -> 2 -> 5 : 5
더 많은 경로가 있지만 (2번으로 갔다가 4번 갔다가...) 중복되는 경로를 제하면 전체적으로 intensity는 4가 되네요
여기서 포인트, 출입구 -> 산봉우리 를 계산했는데 왜 산봉우리 -> 출입구를 계산 안하는가???
왜냐하면, 출입구 -> 산봉우리 최소를 찾고나면, 산봉우리 -> 출입구는 똑같은 경로를 그대로 돌아오면 되기 때문에, 출입구 -> 산봉우리만 찾으면 됩니다!!
따라서 1번 문제의 result는 5번 산봉우리에, intensity 3 입니다!
이제 문제를 이해했으니 전체 input을 볼까요?
gates, summits는 출입구, 산봉우리 인데, paths의 형태를 좀 볼까요??
i, j, w 로 들어오고 있고, 각각이 from, to, cost로 보면 되겠군
이 이미지를 예시로 들면 [3, 2, 5]로 들어오겠군요
비즈니스 로직
이번엔 도메인을 정의하기 전에, 어떤 알고리즘을 쓸 지 생각해볼게요!
우선 이 문제는 "경로 탐색 + 가중치 부여" 문제입니다. A -> B 까지 가는데 있어 가는 모든 경로를 찾고, 가중치를 고려해서 최적의 경로를 찾아야 합니다.
이런 문제를 해결하는데 가장 대표적인 알고리즘이 있죠! 다익스트라 알고리즘입니다!!
다익스트라 알고리즘은 쉽게 말하면 BFS + Priority Queue 방식으로 구현하는 방식으로 단일 시작점에서 모든 노드까지의 최단 경로를 구하는 알고리즘 입니다.
핵심 원리는 아래와 같습니다.
1) 시작점으로 부터 거리를 무한대로 초기화
2) 시작 정점의 거리는 0으로 초기화
3) 방문하지 않은 정점 중 최소 거리를 가진 노드를 선택
4) 해당 노드를 거쳐 가는 경로가 더 짧다면 거리 갱신
5) 모든 노드를 방문할 때 까지 반복
대충 kotlin 코드로 짜면 아래와 같습니다.
import java.util.PriorityQueue
data class Edge(val node: Int, val cost: Int)
data class Node(val node: Int, val distance: Int) : Comparable<Node> {
override fun compareTo(other: Node): Int {
return this.distance - other.distance
}
}
fun dijkstra(start: Int, graph: List<MutableList<Edge>>): IntArray {
// 1. 시작점으로 부터 모든 거리를 무한대로 초기화
val distance = IntArray(graph.size) { Int.MAX_VALUE }
val pq = PriorityQueue<Node>()
// 2. 시작 정점의 거리는 0으로 초기화
distance[start] = 0
pq.add(Node(start, 0))
// 5.모든 노드를 방문할 때 까지 반복
while (pq.isNotEmpty()) {
val current = pq.poll()
val currentNode = current.node
val currentDistance = current.distance
if (currentDistance > distance[currentNode]) continue
// 3. 방문하지 않은 정점 중 최소 거리를 가진 노드를 선택
for (edge in graph[currentNode]) {
val newDistance = distance[currentNode] + edge.cost
// 4.해당 노드를 거쳐 가는 경로가 더 짧다면 거리 갱신
if (newDistance < distance[edge.node]) {
distance[edge.node] = newDistance
pq.add(Node(edge.node, newDistance))
}
}
}
return distance
}
// 예시 실행
fun main() {
val V = 5 // 노드 개수
val graph = List(V + 1) { mutableListOf<Edge>() }
// 그래프 초기화 (1-based index)
graph[1].add(Edge(2, 2))
graph[1].add(Edge(3, 5))
graph[2].add(Edge(3, 1))
graph[2].add(Edge(4, 2))
graph[3].add(Edge(4, 3))
graph[4].add(Edge(5, 1))
val start = 1
val result = dijkstra(start, graph)
for (i in 1..V) {
if (result[i] == Int.MAX_VALUE) {
println("노드 $i : 도달 불가")
} else {
println("노드 $i : 최단 거리 = ${result[i]}")
}
}
}
이제 이 알고리즘 코드를 베이스로 oop 스럽게 도메인을 한번 입혀볼까요??
우선 해당 문제에서 핵심 용어부터 뽑아볼게요
1) 출입구, 산봉우리, 쉼터
2) 등산로
3) intensity
이렇게 뽑아낼 수 있는데, 출입구, 산봉우리, 쉼터 이 개념은 지점으로 타입이 분리된 걸로 볼 수 있겠군요, 그러면 TrailPoint 객체로 묶어서 처리할 수 있겠습니다.
그리고 등산로, 등산로는 각 지점을 연결하는 간선 개념이에요 따라서 Trail(등산로) 라는 개념으로 각각의 포인트를 묶어주는 역할로 잡읍시다
intensity는 각 등산로의 강도로 Trail의 멤버 변수로 가지고 있으면 딱이겠네요
그리고 이 모든걸 아우르는 산(Mountain)이라는 객체를 만들어볼까합니다. 등산이라는 네이밍으로 하려다가 "산에, 등산로와 쉼터, 포인트가 있다!" 라는 개념이 더 좋을 거 같네요!
음 산이라는 객체가 있고, 그 산의 등산로들의 Intensity를 계산해주는 Calculator 객체가 있으면 좋을 거 같습니다.
왜냐하면 산(Mountain)은 말 그대로 등산로와 출입구, 산봉우리, 쉼터 같은 정보를 담고 있는 그림판 같은 역할이라고 보면 될 것 같거든요.
거기서 뭔가 계산을 하기 시작하면 점점 역할이 꼬이게 되니까, 계산은 계산 전용 객체한테 맡기는 게 깔끔하다고 생각합니다.
나중에 intensity의 평균이나 총합 같은 추가 기능이 생긴다고 해도, 그건 산이 아니라 계산기(Calculator) 가 할 일이라고 보는 게 유지보수나 확장에도 더 유리할 것 같거든요!
고민 흔적 남기기
도메인 구조를 먼저 고민하고 나니, “이걸 다익스트라 알고리즘에 어떻게 적용하지?” 라는 고민이 들었습니다.
다익스트라 알고리즘은 크게 두 가지 전제가 필요합니다:
1) 우선순위 큐에 들어갈 수 있어야 하고,
2) 이 문제에서는 경로의 길이가 아니라 경로 중 가장 힘든 구간의 강도(intensity) 가 중요하다는 점입니다.
처음엔 Trail 객체를 우선순위 큐에 그대로 넣을까 했는데, 여기서 혼란이 생겼습니다.
Trail은 하나의 등산로를 의미하고, 그 안의 cost는 "해당 구간 하나의 강도"를 의미합니다.
하지만 우리가 큐에 넣고 관리해야 하는 값은 "지금까지 지나온 경로에서의 최대 강도", 즉 누적된 intensity인 거죠.
이걸 Trail에 억지로 끼워 넣기엔 역할이 애매해졌고, 결국 저는 경로상의 현재 intensity 상태를 따로 담는 IntensityNode 객체를 만들어 이 문제를 풀기로 했습니다. 이 객체는 Comparable을 구현해, intensity가 작은 노드부터 먼저 탐색되도록 했고요.
이렇게 해서 도메인은 도메인대로 깔끔하게 유지하고, 알고리즘 로직은 별도의 객체로 분리해 명확하게 처리할 수 있었습니다.
그러면 아래와 같은 class 들이 만들어집니다.
// 지점 간 경로
data class Trail(
val target: TrailPoint,
val cost: Int
)
// 등산 지점 노드
class TrailPoint(val id: Int) {
private val connections = mutableListOf<Trail>()
}
// 전체 산 구조 (그래프)
class Mountain(
val gates: Set<Int>,
val summits: Set<Int>
) {
val points: MutableMap<Int, TrailPoint> = mutableMapOf()
}
// -------------알고리즘 구현 용-------------
// 우선순위 큐 노드
data class IntensityNode(
val node: TrailPoint,
val intensity: Int
) : Comparable<IntensityNode> {
override fun compareTo(other: IntensityNode): Int {
return this.intensity - other.intensity
}
}
// Intensity 계산
object IntensityCalculator {
fun calculateFromAllGates(mountain: Mountain): Result {}
}구현
Trail, TrailPoint, Mountain을 초기화 하는 부분은 크게 어렵지 않습니다! 값을 읽어와서 매핑하는게 다죠!!
// 지점 간 경로
data class Trail(
val target: TrailPoint,
val cost: Int
)
// 등산 지점 노드
data class TrailPoint(val id: Int) {
private val connections = mutableListOf<Trail>()
fun connectTo(target: TrailPoint, cost: Int) {
connections.add(Trail(target, cost))
}
fun getConnections(): List<Trail> = connections
}
// 전체 산 구조 (그래프)
data class Mountain(
val gates: Set<Int>,
val summits: Set<Int>
) {
private val points: MutableMap<Int, TrailPoint> = mutableMapOf()
fun addPath(from: Int, to: Int, cost: Int) {
val fromPoint = points.getOrPut(from) { TrailPoint(from) }
val toPoint = points.getOrPut(to) { TrailPoint(to) }
fromPoint.connectTo(toPoint, cost)
toPoint.connectTo(fromPoint, cost)
}
fun getPoint(id: Int): TrailPoint? = points[id]
}
//-- 실제 사용 --
val mountain = Mountain(
gates = gates.toSet(),
summits = summits.toSet()
).apply {
paths.forEach {
addPath(
from = it[0],
to = it[1],
cost = it[2]
)
}
}
그 다음에는 다익스트라 알고리즘을 구현해보려고 합니다.
여기서 고려해야할 점은 크게 두 가지였어요
1) 성능
2) 중복
기본적인 다익스트라 알고리즘은 하나의 시작점(start point) 을 기준으로 최소 비용 경로를 찾는 알고리즘입니다. 하지만 이 문제에서는 여러 개의 시작점(gates) 이 존재하죠. 만약 이를 일반적인 방식으로 처리한다면, 시작점마다 다익스트라를 돌려야 하므로 시간 복잡도는 O(M × E × log V)가 됩니다. (M = gate 개수) 문제에서 gate는 최대 50,000개까지 될 수 있기 때문에, 이 방식은 성능적으로 매우 부담됩니다.
그런데 사실 중요한 건, 모든 시작점에서 산봉우리까지의 경로를 전부 탐색하는 게 아니라, 가장 낮은 intensity로 도달할 수 있는 단 하나의 산봉우리만 찾으면 된다는 점이에요.
그래서 우리는 다익스트라를 "시작점 M개를 동시에 시작하는" 방식으로 구현하면 됩니다. 즉, 큐에 M개의 시작점을 한꺼번에 넣고, 그 중 가장 intensity가 낮은 경로부터 우선 탐색하는 구조로 만들면, 결국 하나의 다익스트라 탐색으로 모든 gate를 커버할 수 있게 됩니다. 시간복잡도는 O(E × log V)로 줄어듭니다.
문제 설명에서는 "산봉우리 하나를 다녀와서 출입구로 돌아온다"라고 되어 있지만, 사실상 왕복 경로를 직접 구성할 필요는 없습니다. 이유는? 갈 때 intensity가 최소였다면, 돌아올 때도 그 intensity 이하로 돌아오는 것이 가능하기 때문입니다.
즉, 실제로는 편도만 고려해도 충분하며, 왕복 경로를 직접 다룰 필요가 없습니다. 만약 진짜 왕복 경로를 다 돌게 되면 시간복잡도는 O(M × N × E × log V)까지 올라가 버립니다. 비효율적이죠.
마지막으로, 산봉우리 조건도 체크해야 합니다. 산봉우리는 한 번만 방문해야 하므로, 산봉우리에 도달하면 그 이후 탐색은 하지 않고 즉시 멈추는 방식이 맞습니다. 이를 통해 탐색해야 할 정점(V)과 간선(E)의 수를 자연스럽게 줄일 수 있어요.
따라서 이 모든 걸 고려한 intensicy calculator 형태는 아래와 같습니다
// 결과 표현용 data class
data class Result(val gate: Int, val summit: Int, val intensity: Int)
// 우선순위 큐 노드
data class IntensityNode(
val node: TrailPoint,
val intensity: Int
) : Comparable<IntensityNode> {
override fun compareTo(other: IntensityNode): Int {
return this.intensity - other.intensity
}
}
// Intensity 계산
object IntensityCalculator {
fun calculateFromAllGates(mountain: Mountain): Result {
val pq = PriorityQueue<IntensityNode>()
val intensities = mutableMapOf<Int, Int>().withDefault { Int.MAX_VALUE }
// 모든 시작점 한번에 주입
for (gate in mountain.gates) {
val point = mountain.getPoint(gate) ?: continue
intensities[gate] = 0
pq.add(IntensityNode(point, 0))
}
while (pq.isNotEmpty()) {
val current = pq.poll()
val currentId = current.node.id
val currentIntensity = current.intensity
// 산봉우리에 도달했으면 더 이상 확장하지 않음 (하나만 방문 가능하므로)
if (currentId in mountain.summits) continue
// 이미 더 낮은 intensity로 방문한 적이 있다면 skip
if (currentIntensity > intensities.getValue(currentId)) continue
// 연결된 모든 지점을 확인하며 intensity 업데이트
for (trail in current.node.getConnections()) {
val next = trail.target.id
val nextIntensity = max(currentIntensity, trail.cost)
if (nextIntensity < intensities.getValue(next)) {
intensities[next] = nextIntensity
pq.add(IntensityNode(trail.target, nextIntensity))
}
}
}
// 도달 가능한 산봉우리 중 intensity가 가장 낮은 경로 선택
return mountain.summits
.map { Result(0, it, intensities.getValue(it)) }
.filter { it.intensity < Int.MAX_VALUE }
.minWithOrNull(compareBy<Result> { it.intensity }.thenBy { it.summit })!!
}
}제출
네! 문제를 제출하니 잘 풀리는군요!! 실제로는 알고리즘을 풀 때 바로 정답을 내진 못했습니다
우선 처음에는 bfs로 싹 다 돌면서 경로 가중치를 계산했는데 일부 예외 케이스를 찾아내지 못했습니다. 그래서 우선 순위 큐를 도입해서 가중치 계산 부분 로직을 쉽게 다시 구현을 했고 정확도 문제는 해결됐습니다!
그러나 실제 모든 시작점을 다 돌면서 가중치 계산을 했기 때문에 시간 초과가 뜨더라구요! 그래서 한번에 다 넣고 알고리즘을 돌려 푸는 방식으로 시간 초과 문제도 해결했습니다!
역시 문제는 한번에 풀기가 가장 어렵군요!
전체 코드 남기고 오늘 포스팅을 마무리하겠습니다!!
import java.util.PriorityQueue
import kotlin.math.max
// 지점 간 경로
data class Trail(
val target: TrailPoint,
val cost: Int
)
// 등산 지점 노드
data class TrailPoint(val id: Int) {
private val connections = mutableListOf<Trail>()
fun connectTo(target: TrailPoint, cost: Int) {
connections.add(Trail(target, cost))
}
fun getConnections(): List<Trail> = connections
}
// 전체 산 구조 (그래프)
data class Mountain(
val gates: Set<Int>,
val summits: Set<Int>
) {
private val points: MutableMap<Int, TrailPoint> = mutableMapOf()
fun addPath(from: Int, to: Int, cost: Int) {
val fromPoint = points.getOrPut(from) { TrailPoint(from) }
val toPoint = points.getOrPut(to) { TrailPoint(to) }
fromPoint.connectTo(toPoint, cost)
toPoint.connectTo(fromPoint, cost)
}
fun getPoint(id: Int): TrailPoint? = points[id]
}
// -------------알고리즘 구현 용-------------
// 결과 표현용 data class
data class Result(val gate: Int, val summit: Int, val intensity: Int)
// 우선순위 큐 노드
data class IntensityNode(
val node: TrailPoint,
val intensity: Int
) : Comparable<IntensityNode> {
override fun compareTo(other: IntensityNode): Int {
return this.intensity - other.intensity
}
}
// Intensity 계산
object IntensityCalculator {
fun calculateFromAllGates(mountain: Mountain): Result {
val pq = PriorityQueue<IntensityNode>()
val intensities = mutableMapOf<Int, Int>().withDefault { Int.MAX_VALUE }
// 모든 시작점 한번에 주입
for (gate in mountain.gates) {
val point = mountain.getPoint(gate) ?: continue
intensities[gate] = 0
pq.add(IntensityNode(point, 0))
}
while (pq.isNotEmpty()) {
val current = pq.poll()
val currentId = current.node.id
val currentIntensity = current.intensity
// 산봉우리에 도달했으면 더 이상 확장하지 않음 (하나만 방문 가능하므로)
if (currentId in mountain.summits) continue
// 이미 더 낮은 intensity로 방문한 적이 있다면 skip
if (currentIntensity > intensities.getValue(currentId)) continue
// 연결된 모든 지점을 확인하며 intensity 업데이트
for (trail in current.node.getConnections()) {
val next = trail.target.id
val nextIntensity = max(currentIntensity, trail.cost)
if (nextIntensity < intensities.getValue(next)) {
intensities[next] = nextIntensity
pq.add(IntensityNode(trail.target, nextIntensity))
}
}
}
// 도달 가능한 산봉우리 중 intensity가 가장 낮은 경로 선택
return mountain.summits
.map { Result(0, it, intensities.getValue(it)) }
.filter { it.intensity < Int.MAX_VALUE }
.minWithOrNull(compareBy<Result> { it.intensity }.thenBy { it.summit })!!
}
}
fun main() {
data class TestCase(
val paths: List<List<Int>>,
val gates: List<Int>,
val summits: List<Int>,
val expected: List<Int>
)
val testCases = listOf(
TestCase(
paths = listOf(
listOf(1, 2, 3), listOf(2, 3, 5), listOf(2, 4, 2), listOf(2, 5, 4),
listOf(3, 4, 4), listOf(4, 5, 3), listOf(4, 6, 1), listOf(5, 6, 1)
),
gates = listOf(1, 3),
summits = listOf(5),
expected = listOf(5, 3)
),
TestCase(
paths = listOf(
listOf(1, 4, 4), listOf(1, 6, 1), listOf(1, 7, 3),
listOf(2, 5, 2), listOf(3, 7, 4), listOf(5, 6, 6)
),
gates = listOf(1),
summits = listOf(2, 3, 4),
expected = listOf(3, 4)
),
TestCase(
paths = listOf(
listOf(1, 2, 5), listOf(1, 4, 1), listOf(2, 3, 1),
listOf(2, 6, 7), listOf(4, 5, 1), listOf(5, 6, 1), listOf(6, 7, 1)
),
gates = listOf(3, 7),
summits = listOf(1, 5),
expected = listOf(5, 1)
),
TestCase(
paths = listOf(
listOf(1, 3, 10), listOf(1, 4, 20),
listOf(2, 3, 4), listOf(2, 4, 6),
listOf(3, 5, 20), listOf(4, 5, 6)
),
gates = listOf(1, 2),
summits = listOf(5),
expected = listOf(5, 6)
)
)
testCases.forEachIndexed { index, (paths, gates, summits, expected) ->
val mountain = Mountain(
gates = gates.toSet(),
summits = summits.toSet()
).apply {
paths.forEach {
addPath(
from = it[0],
to = it[1],
cost = it[2]
)
}
}
val result = IntensityCalculator
.calculateFromAllGates(mountain)
println("Test #$index result: $result, expected: ${expected}")
}
}
