[백준][코틀린][16947] 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

문제 풀이

1. 문제의 조건에서 순환선이 되는 경우를 찾고 순환선에 포함되는 역을 구한다.

2. 역과 역간의 정보를 연결 리스트로 저장한다.

3. 역 1번부터 N 번까지 DFS 로 탐색하여 순환선이 되는 경우에 대해서 포함되는 역을 찾는 탐색을 한다.

3-1. 현재 역(current), 순환 지점 역(taget), 이전 역(prev) 를 매개변수로 하여 탐색한다.

3-2. 이때 현재역과 연결되어 다음역이 순환 지점역과 같으면서 이전역과 순환 지점역이 다른 경우에는 순환선에 해당하는 역이 된다.

4. N번역까지 탐색하여 순환선에 대한 되는 역을 queue 에 저장한다.

5. 저장된 queue 를 이용하여 BFS 를 통해서 순환선에 포함된 역과의 거리를 구한다.

5-1. Int 배열의 result 에 순환선에 포함된 역을 0으로 저장하고 나머지는 -1로 저장한다.

5-2. 순환선에 포함된 역은 이미 방문한 것으로 간주하여 visit 배열에서 해당되는 역을 true 업데이트 한다. 거리가 변하지 않기 때문이다.

5-3. 다음 역은 현재 역의 값에 1을 더해 준다.

코드

import java.io.*
import java.util.*

private var circular = false
private val result = IntArray(3001) {
    -1
}

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val map = Array(N + 1) {
        ArrayList<Int>()
    }

    repeat(N) {
        val (a, b) = br.readLine().split(" ").map { it.toInt() }
        map[a].add(b)
        map[b].add(a)
    }

    for (i in 1..N) {
        val visit = BooleanArray(N + 1) { false }
        circular = false
        dfs(N, map, visit, i, i, 0)
    }

    /*println("circular way >>>")
    for (i in 1..N) {
        print("${result[i] }")
    }
    println()*/


    val visit = BooleanArray(N + 1) {
        false
    }

    val queue = LinkedList<Int>()

    for (i in 1..N) {
        if (result[i] == 0) {
            queue.add(i)
            visit[i] = true
        }
    }

    distance(map, visit, queue)

    for (i in 1..N) {
        print("${result[i]} ")
    }

    println()
}

private fun dfs(N: Int, map: Array<ArrayList<Int>>, visit: BooleanArray, current: Int, target: Int, prev: Int) {
    visit[current] = true

    for (next in map[current]) {
        //println("dfs: $current, $target, $prev, $next, $circular, ${visit[next]}")

        if (!visit[next]) {
            visit[next] = true
            dfs(N, map, visit, next, target, current)
        } else if (next == target && target != prev) {
            circular = true
            result[next] = 0
            return
        }
    }
}

private fun distance(map: Array<ArrayList<Int>>, visit: BooleanArray, queue: LinkedList<Int>) {
    //println("queue > $queue")

    while (queue.isNotEmpty()) {
        val current = queue.pop()
        visit[current] = true
        //println("current > $current")

        for (next in map[current]) {
            if (visit[next]) continue
            //println("next : $next, result[$current] : ${result[current]}")
            queue.add(next)
            visit[next] = true
            result[next] = result[current] + 1
        }
    }
}