[BOJ/Gold 4] 백준 23835 어떤 우유의 배달목록 (Easy)(Kotlin)

문제 링크

https://www.acmicpc.net/problem/23835

23835번: 어떤 우유의 배달목록 (Easy)

 

문제

이 문제는 "어떤 우유의 배달목록 (Hard)" 문제와 N, Q의 제한을 제외하고 같은 문제이다.

SASA의 기숙사에는 N개의 방과 사감의 감시를 피하기 위해 만든 N - 1개의 비밀 통로가 존재한다. 각 방은 1번부터 N번까지의 번호가 붙어있다. 비밀 통로는 서로 다른 두 방을 양방향으로 연결하며, 임의의 두 방 사이를 비밀 통로를 통해 같은 방을 여러 번 지나지 않고 이동할 수 있는 경로가 정확히 한 개 있다. 우유 배달을 하는 태영이는 선배들의 주문을 여럿 받아서 우유를 배달한다.

각 주문은 출발하는 방과 도착하는 방으로 이루어져 있다. 태영이는 출발하는 방에서 도착하는 방까지의 경로에 있는 모든 방에 우유를 배달하며, 출발하는 방을 제외하고 i번째로 방문하는 방에 i개의 우유를 배달한다.

태영이는 정신 없이 우유 배달을 하느라 우유를 얼마나 배달했는지 기억나지 않는다. 이제까지 배달한 우유의 수를 보고해야 하는 태영이를 위해, 실시간으로 배달한 우유의 수를 구하는 프로그램을 작성해주자. 해당 프로그램은 다음 두 종류의 쿼리를 처리해야 한다.

• 1 u v: 태영이가 주문을 받아, 우유를 u번 방부터 v번 방까지 배달한다.
• 2 x: 태영이가 지금까지 x번 방에 배달한 우유의 총 개수를 출력한다.

 

입력

첫째 줄에 방의 개수 N이 주어진다.

둘째 줄부터 N - 1개의 줄의 i번째 줄에는 ai와 bi가 공백으로 구분되어 주어지며, 이는 ai번 방과 bi번 방이 비밀 통로로 연결되어 있다는 것을 의미한다.

 N + 1번째 줄에는, 쿼리의 개수 Q가 주어진다.

다음 Q개의 줄에는 i번째 줄에는 i번째 쿼리가 다음과 같은 형태로 주어진다.

• 1번 쿼리는 ti = 1, 출발하는 방의 번호 ui 도착하는 방의 번호 vi가 공백으로 구분되어 주어진다.
• 2번 쿼리는 ti = 2와 지금까지 배달한 우유의 총 개수를 계산해야 하는 방의 번호 xi가 공백으로 구분되어 주어진다.

 

출력

2번 쿼리의 결과를 한 줄에 하나씩 차례대로 출력한다.

 

제한

•  1 ≤ N, Q ≤ 1,000
•  1 ≤ ai, bi ≤ N(1 ≤ i ≤ N − 1)
• 임의의 두 방 사이를 비밀 통로를 통해 같은 방을 여러 번 지나지 않고 이동할 수 있는 경로가 정확히 한 개 있다.
•  ti = 1일 때, 1 ≤ ui, vi ≤ N (1 ≤ i ≤ N)
•  ti = 1일 때, ui ≠ vi (1 ≤ i ≤ N)
•  ti = 2일 때, 1 ≤ xi ≤ N
•  ti = 2인 쿼리가 한 개 이상 주어진다.

 

예제 입력 1

5
1 2
2 3
3 4
2 5
5
1 3 5
1 4 5
1 1 2
2 2
2 5

예제 출력 1

4
5

 

 

알고리즘 분류

• 자료 구조
• 그래프 탐색

 

풀이

먼저 N - 1개의 간선 정보를 입력받으면서 트리를 구성한다.

그리고 Q개의 쿼리문을 입력받으면서 T가 1이면 u부터 v까지의 단 하나의 경로를 찾아 DFS를 수행한다.

같은 방 여러 곳을 지나지 않고 u부터 v까지 갈 수 있는 경로는 단 하나만 존재하므로, 이미 왔던 방을 다시 간다면 해당 경로로는 다시 가지 않도록 하면서 몇 번째에 어느 방을 지나쳤는지를 route에 기록한다.

v까지 도달했다면 단 하나의 경로를 찾았다는 뜻이므로 route에 기록된 방에 따라 i번째로 지나친 방에는 i - 1개의 우유를 추가한다.

T가 2면 현재까지 x번 방에 몇 개의 우유를 추가했는지 출력한다.

 

코드

import java.util.*

var arr: Array<List<Int>> = Array(1001) { listOf() }
var route: Array<Int> = Array(1001) { 0 }
val milk: Array<Int> = Array(1001) { 0 }

fun dfs(now: Int, prev: Int, end: Int, count: Int): Boolean {
    route[count] = now
    if (now == end) {
        for (i in 0 .. count) {
            milk[route[i]] += i
        }
        return true
    }

    var flag: Boolean = false
    for (i in arr[now]) {
        if (i == prev) {
            continue
        }
        if (dfs(i, now, end, count + 1)) {
            flag = true
        }
    }

    return flag
}

fun main() = with(Scanner(System.`in`)) {
    val n = nextLine().toInt()
    for (i in 0 until n - 1) {
        val s = nextLine().split(' ')
        val a = s[0].toInt()
        val b = s[1].toInt()
        arr[a] = arr[a].plus(b)
        arr[b] = arr[b].plus(a)
    }
    val q = nextLine().toInt()
    for (i in 0 until q) {
        val s = nextLine().split(' ')
        if (s[0] == "1") {
            val u = s[1].toInt()
            val v = s[2].toInt()
            dfs(u, 0, v, 0)
        }
        else {
            val x = s[1].toInt()
            println(milk[x])
        }
    }
}