Kotlin] 백준 2606 풀이

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

 

 

이 문제는 연결된 노드를 탐색하기만 하면 되서 깊이 탐색이든 넓이 탐색이든 편한대로 사용하면 된다.

글쓴이는 깊이 탐색으로 풀었음 ^-^

https://itstudy-mary.tistory.com/595

깊이 우선 탐색법(with. kotlin)

 

 

(개인적으로) 이 문제에서 걸린 점은 연결은 양방향이라는 점인데.. 그래서 그래프에서 연결된 양 옆 다 연결된 노드를 필터링 해서 풀었다.

(근데 이럴거 같으면 사실 노드 + 1의 배열 하나 만들어놓고, 배열 내에 양방향으로 집어넣는게 낫지 않았나 하는 생각도 듭니다 ^-^)

이걸 제외하면 정말 기초적인 탐색 알고리즘 문제입니다.

 

아래의 코드를 보면..

import java.util.Stack

fun main(args: Array<String>) {
    question2606()
}

fun question2606() {
    val computer = readln().toInt()
    // 0번 컴퓨터는 계산 편하라고 넣은 거임!!;;
    val nodeCount = readln().toInt()
    val graph = mutableListOf<List<Int>>()
    val computerVisited = Array(computer + 1) { false }
    val stack = Stack<Int>()


    for (i in 1 .. nodeCount) {
        val node = readln().split(" ").map { it.toInt() }
        graph.add(node)
    }

    // 1번 컴퓨터와 인접한 노드가 없다면 바로 1개 리턴 해야함..
    if(graph.count { it[0] == 1 || it[1] == 1} == 0) {
        println(0)
    } else {
        stack.push(1)
        computerVisited[1] = true

        while (!stack.empty()) {
            println(stack)
            val nodeIndex = stack.pop()
            // 양방향 필터
            val nodeConnect = graph.filter { it[0] == nodeIndex || it[1] == nodeIndex }
            nodeConnect.forEach {
                val destination = it.filter { it != nodeIndex }[0]
                if(!computerVisited[destination]) {
                    stack.push(destination)
                    computerVisited[destination] = true
                }
            }
        }
        println(computerVisited.count { it } - 1)

    }



}

( 양방향 생각 안한 빡머갈 인증)