백준 16940 BFS 스페셜 저지 Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

문제

BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.

정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, BFS 알고리즘은 다음과 같은 형태로 이루어져 있다.

1. 큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다.
2. 큐가 비어 있지 않은 동안 다음을 반복한다.
   1. 큐에 들어있는 첫 정점을 큐에서 꺼낸다. 이 정점을 x라고 하자.
   2. x와 연결되어 있으면, 아직 방문하지 않은 정점 y를 모두 큐에 넣는다. 모든 y를 방문했다고 처리한다.

2-2 단계에서 방문하지 않은 정점을 방문하는 순서는 중요하지 않다. 따라서, BFS의 결과는 여러가지가 나올 수 있다.

트리가 주어졌을 때, 올바른 BFS 방문 순서인지 구해보자.

입력

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 BFS 방문 순서가 주어진다. BFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

출력

입력으로 주어진 BFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

fun bfs(n: Int): Int{
    val q: Queue<Int> =  LinkedList()
    q.add(1)
    var idx=1
    if(order[0]!=1) return 0
    while(q.isNotEmpty()){
        val size = q.size
        val numSet = BooleanArray(n+1)
        for(i in 0 until size){
            val cur = q.poll()
            for(next in edge[cur]){
                if(visited[next]) continue
                numSet[next] = true
                visited[next] =true
                q.add(next)
            }
        }
        while(idx<n){
            if(numSet[order[idx]]) idx++
            else break
        }
    }
    if(idx==n) return 1
    return 0
}

처음엔 bfs를 이렇게 짰다.

트리의 각 뎁스 내에서만 값이 유효한지 확인했는데, 계속 틀려서 찾아보니 뎁스 뿐만 아니라 해당 뎁스에서 어떤 노드를 먼저 방문하느냐에 따라 전체 순서가 달라진다는 것을 알았다.

 

위의 트리를 보자 ㅎㅎ 맥북으로 갈아타서 Keynote란 걸 써봤는데 아직 익숙치 않다.

입력이 1,3,2,4,5,6로 주어진다면 뎁스 1인 2와 3 노드까지는 문제가 없다.

하지만 3을 먼저 방문하기 때문에 1, 3, 2, 6, 4, 5가 맞는 입력이므로 답은 0이다.

하지만 위의 코드를 돌린다면 뎁스마다 값은 잘 들어있기 때문에 1이란 답이 나와 틀리게 된다.

 

그럼 1,3,2,4,5,6이란 순서가 맞는지 어떻게 검증할 수 있을까?

우선 간선이 다음과 같이 들어왔다고 하자.

1: 2,3

2: 1,4,5

3 : 1,6

4 : 2

5 : 2

6 : 3

여기서 순서가 달라질 수 있는 부분은 1->2,3  2->4,5 두 부분이다.
입력이 1,3,2,4,5,6으로 들어왔다면 1 이후에 3,2이므로 2보다 3이 먼저 와야 하고, 2 이후에 4,5이므로 5보다 4가 먼저 와야 한다.

이에 맞게 간선을 바꿔주면

1: 3,2

2: 1,4,5

3: 1,6

4: 2

5: 2

6: 3

 

이제 이 간선 정보로 bfs를 돌리면 결과는 1, 3, 2, 6, 4, 5 이므로 주어진 입력은 틀린 답이란 걸 알 수 있다.

 

위의 과정에서 우리는 간선들을 주어진 입력 순서를 기준으로 정렬하였다.

이를 구현하는 방법은 다음과 같다.

node	0	1	2	3	4	5	6
order	0	0	2	1	4	5	3

 위 그래프 처럼 order라는 배열을 하나 만들고, 주어진 입력을 이용해 각 노드에 대해 우선순위를 저장한다.

이후 우리가 만든 이 우선순위로 정렬을 커스텀하여 간선들을 정렬한다.

 

이후 정렬된 간선으로 bfs를 돌려 처음 주어진 입력 값과 같게 나온다면 1을 출력, 아니라면 0을 출력한다. 

 

요약하면

1. 입력받은 순서를 저장한다.(정렬용, 정답 비교용 두 가지를 저장했다.)

2. 입력받은 순서로 간선들을 정렬한다.

3. 정렬된 간선들로 bfs를 돌려 처음 입력 받은 순서와 비교하여 정답을 출력한다.

코드

import java.util.*

val br = System.`in`.bufferedReader()
lateinit var edge: Array<ArrayList<Int>>
lateinit var visited: BooleanArray
lateinit var originOrder: IntArray
lateinit var order: IntArray

fun bfs(n: Int): Int {
    val q: Queue<Int> = LinkedList()
    q.add(1)

    visited[1] = true
    if (originOrder[0] != 1) return 0
    val newOrder = IntArray(n)
    newOrder[0] = 1
    var idx=1
    while (q.isNotEmpty()) {
        val cur = q.poll()
        for (next in edge[cur]) {
            if (visited[next]) continue
            visited[next] = true
            newOrder[idx++] = next
            q.add(next)
        }

    }

    for(i in newOrder.indices){
        if(newOrder[i]!= originOrder[i]) return 0
    }
    return 1
}

fun main() = with(System.out.bufferedWriter()) {

    //input
    val n = br.readLine().toInt()
    visited = BooleanArray(n + 1)
    edge = Array(n + 1) { ArrayList() }
    repeat(n - 1) {
        br.readLine().split(' ').map { it.toInt() }.apply {
            edge[this[0]].add(this[1])
            edge[this[1]].add(this[0])
        }
    }
    val tk = StringTokenizer(br.readLine())
    order = IntArray(n + 1)
    originOrder = IntArray(n)
    var idx=0
    while(tk.hasMoreTokens()){
        val num =tk.nextToken().toInt()
        originOrder[idx] = num
        order[num]= idx++
    }

    //sort
    for (i in 1..n) {
        edge[i].sortWith { a, b ->
            when {
                order[a] < order[b] -> -1
                else -> 1
            }
        }
    }

    //solve, output
    write("${bfs(n)}")

    close()
}