[Kotlin] 백준 4803번 : 트리 <Gold 4>

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

4803번: 트리

Code

---

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var case = 0

    while (true) {
        val (n, m) = readLine().split(" ").map { it.toInt() }
        
        if (n == 0 && m == 0) break
        case++

        val graph = Array(n + 1) { LinkedList<Int>() }
        val visited = BooleanArray(n + 1)
        var treeCnt = 0

        repeat(m) {
            val (node1, node2) = readLine().split(" ").map { it.toInt() }

            graph[node1].add(node2)
            graph[node2].add(node1)
        }

        for (i in 1 .. n){
            if (!visited[i] && isCycle(graph, visited, i, 0))
                treeCnt++
        }

        bw.write("Case $case: ")
        when(treeCnt){
            0 -> bw.write("No trees.")
            1 -> bw.write("There is one tree.")
            else -> bw.write("A forest of ${treeCnt} trees.")
        }
        bw.write("\n")
    }

    bw.flush()
    bw.close()
}

fun isCycle(graph: Array<LinkedList<Int>>, visited: BooleanArray, now: Int, before: Int): Boolean{
    if (visited[now])
        return false

    var result = true
    visited[now] = true

    graph[now].forEach{ next->
        if (next != before)
            result = (result && isCycle(graph, visited, next, now))
    }

    return result
}

 

---

문제를 이해하는데 시간이 걸렸었다

 

처음에는 그래프의 수를 말하는 건가? 싶어서 DFS를 약간 변형하여 돌려보면서 숫자를 셋었다.

1부터 n까지 DFS를 실행시키면서 visite하지 않았다면 treeCnt를 하나 늘려주며 DFS를 실행시켰었다.

근데 답이 안나오네?

 

그래서 문제를 다시 읽었다. 트리의 갯수를 세는건데 정점이 n개, 간선이 n-1개 있다고 한다.

아! 그러면 여러개로 나눠져있는 그래프가 정점의 갯수와 간선의 갯수를 이용해서 트리인지 확인하면 되는거네.

 

그래서 아래가 사고의 과정이다.

/*
트리의 조건 : 정점 = n개, 간선은 n-1개

-> 정점을 카운팅하고, 간선을 카운팅하는 함수가 필요하다
-> 연결된걸 쭉 확인해야하니까 DFS로 하자.
-> 정점을 어덯게 확인할까? visited배열을 사용해서 DFS를 쭉 이동시키고, 더이상 이동할게 없다면 cnt를 반환.
   그렇게해서 최종적으로 함수가 반환하는것은 해당 그래프가 가지고 있는 정점의 개수
   근데... 내가 구해야하는건 트리의 정점의 개수니까.. 한번 for문이 끝나면 끝인걸?
   각 그래프 별로 돌려서 해야겠다.
-> 간선은 어떻게 구하지? visited를 무시하고 전부 탐색하기엔.... 무한루프 걸릴거 가튼데
*/

이렇게 생각을 하다가 한 사실을 떠올렸다.

 

정상적으로 연결돼있으면 전부 트리잖아?

정상적으로 연결돼있다는건 위에서 아래로 내려오면서 연결된거고 순환이 아닌 그래프를 말한다는걸 깨달았다.

 

그래서 생각한 아이디어가 그래프 내부에 순환이 존재하는지 파악하는 것이다.

순환이 존재하지 않는다면 정상적인 그래프이므로 트리 일것이고, 순환이 존재한다면 트리가 아닐것이다.

 

그럼 순환이 존재한다는건 어떻게 파악할까?

/*
그래프에서 순환이 발생하려면? 즉 한번 방문한데를 한번 더 방문한다
그러면 그걸 어떻게 체크하지? 배열을 이용해서 지금까지 나왔던 값을 거기에 저장한다.

var result = true
if(!visited[it]){ // 방문하지 않았을 경우
    arr.add(it)
    result = (result == DFS(it))
}else{ // 방문했던 곳 또 왔을 경우
    reult = false
}

return result
*/

이렇게 초기 아이디어를 작성했다.

 

그래서 isCycle이라는 함수를 만들었고, 순환하는지 체크하고자 했다.

아이디어를 발전시키면서 visited하지 않았을때만 DFS를 하려고 했지만, 그렇게 할 경우 순환해서 재방문하는 것을 체크하지 못했다.

그래서 visited는 함수가 실행되면 최 상단에서 체크하여 방문했다면 false를 return하도록 했다.

 

그리고 배열을 이용해서 지금까지 나왔던 값을 기록후, 존재한다면 이동하지 않게 하려고 했다.

근데 이것 또한 문제가 있었다. 순환을 체크 못한다는 것. 그리고 배열을 만든다는 메모리 낭비가 아쉬웠다.

 

고민하다보니 어차피 원래 나왔던 값으로 돌아갔다는것 자체가 visited가 체크해주지 않나? 그러면 내가 굳이 한번 더 체크할 필요가 있나? 라는 생각이 들었다.

바로 실험해봤더니 모든게 false가 나오더라.

 

사실 당연했다.

1과 2가 연결돼있다면

1-2가 연결되고 2-1도 연결돼있다. 그럼 1에서 2로 넘어간 후 다시 1로 넘어오는거다.

 

그럼 이걸 어떻게 체크할까?

이전값과 다음값이 같지만 않으면 되는거잖냐? 이전과 다음이 다른데 사실 순환인 경우는 visited에서 체크해줄 것이다. ex) 1-2-3-4-1

그래서 이전값을 매개변수로 같이 넘겨줬다.

 

그래서 완벽하다 생각하고 실행했는데 값이 이상했다. 

문제는 이 부분이었다.

result = (result == isCycle()) // 귀찮으니 매개변수 생략

 

왜인진 모르겠지만 이부분에서 오류가 발생했고, ==을 &&으로 바꿔주니 정상 작동했다.

 

 

 

 

어려웠다. 

아이디어를 떠올리는데 오래걸렸다.

이 문제에서 가장 큰 포인트는 발상의 전환이었다. 순환이 존재하는지 파악하려 한 것이 제일 유효했다.

그래도 확실히 두문제 연속으로 LinkedList를 활용한 그래프 문제를 푸니까 사용이 편해졌다. 그거에 만족.