[Kotlin, S3] 백준 31409번 착신 전환 소동

출처: unsplash.com

 

착신 전환 소동(31409번)

Silver 3

#그래프 이론 #애드 혹 #해 구성하기 #함수형 그래프

 

문제 내용

 

 

문제 접근

전화기가 주어졌을 때, 착신 전환을 해서 모든 전화기를 먹통으로 만드는 최소의 경우를 구해야 하는 문제이다.

문제 본문의 예시를 들면, A => B, B => C, C => A 순으로 전화를 연결하고 있다.

3개의 전화기가 무한 사이클을 돌고 있다는 것을 알 수 있다.

전화기 여러 개를 무한 사이클을 돌리는 방법은 다양하다.

문제의 입력 예제만 봐도 알 수 있다.

입력 예제 2는 다음과 같이 입력을 받는다.

5
2 1 5 3 4

위 입력값을 그래프로 나타내면 아래와 같다.

사진 1-1

그래프의 전화가 서로 이어져서 무한한 사이클을 형성했다. 이 경우에는 이미 먹통 상태이므로, 바꿔주지 않아도 된다.

 

각 전화기에 연결된 전화기를 확인하기 위해서는 Map을 이용해 어떤 전화에 연결되어 있는지 확인할 필요가 있다.

// graph 구조: key = 전화기 번호, value = 걸려 있는 전화기 번호
private val graph = mutableMapOf<Int, Int>()

 

 

입력 예제 3은 전화기 번호, 연결된 전화기를 map으로 확인해 보면서 파악해 보자.

4
4 4 4 4

입력 예제는 다음과 같고, 전화기의 번호는 입력 순서대로 주어지고, 연결된 전화기는 입력된 값을 뜻한다.

이를 이용해 Map을 구성해 보면 아래와 같다.

{1 : 4,
2 : 4,
3 : 4,
4 : 4}

입력 순으로 전화기 번호가 주어지고, 입력된 값이 전화기 번호이다.

이 예제의 정답을 그래프와 Map으로 나타내보자.

사진 1-2

// 입력 예제 3
{1 : 4,
2 : 4,
3 : 4,
4 : 3}

// 입력 예제 2
{1 : 2,
2 : 1,
3 : 5,
4 : 3,
5 : 4}

위의 경우에도 무한한 사이클이  생성된 것을 볼 수 있다.

위 Map을 보고 하나의 사실을 알 수 있다.

무한 사이클이 적용되기 위해서는 전화기 번호와 연결된 전화기가 같으면 안 된다.
즉, 착신 전환이 걸려 있지 않은 전화기가 없어야 무한 사이클이 형성된다.

이 사실을 이용해 값을 입력받을 때 전화기 번호와 걸려 있는 전화기가 같은지 확인해 주는 작업이 필요하다.

이를 Kotlin 코드로는 다음과 같이 나타낼 수 있다.

 

<조건 1>

i == calling[i]

i가 전화기 번호이고, calling이 현재 연결되어 있는 전화기를 뜻할 때, 전화기 번호와 현재 연결된 전화기가 같으면 착신 전환이 걸려 있는 상태가 아니기 때문에 위 조건을 만족하면 해당 전화기에 다른 전화를 연결해 주면 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cellPhoneCnt = readLine().toInt()
    val calling = mutableListOf(0)
    val phone = readLine().split(" ").map { it.toInt() }
    var changeCnt = 0

    calling.addAll(phone)
    for (i in 1 .. cellPhoneCnt) {
        if (i == calling[i]) {
            val toChange = if (i == cellPhoneCnt) 1 else cellPhoneCnt
            calling[i] = toChange
            changeCnt++
        }
    }

    println(changeCnt)
    println(calling.filter { it != 0 }.joinToString(" "))
}

 

문제 풀이

문제 접근에서는 Map을 예시로 들었지만 해결 코드에서는 List의 index를 현재 전화기 번호로 가정하고, index의 값을 걸려 있는 전화기로 가정하고 문제를 해결했다.

 

calling list에 전화기 번호가 0인 경우는 없으므로 0을 메워 주고, 1번째 index부터 입력된 값을 전부 넣어 준다.

위에 언급한 <조건 1>을 만족한 경우, 기존 연결된 전화를 다른 전화로 바꿔 주어야 한다.

어떤 값으로 바꾸던 상관없기 때문에, 마지막 전화기 번호인 경우에는 1, 그렇지 않을 때는 마지막 전화로 전화를 걸 수 있도록 해주었다.

 

출력할 때는 calling에 0번째 값을 출력하지 않도록 잘 걸러서 출력한다.

 

 

문제 해결 과정

쓸데없이 재귀로 문제를 풀어 보려다가 쓴맛을 보고 위의 문제 해결법을 찾아서 해결한 문제이다.

처음에는 각 전화에 걸려 있는 값으로 계속 재귀로 들어가면서 들어간 값이 착신 전환이 안된 전화인 경우에만 값을 변경해 주었다. 그렇게 하니까 94%쯤에서 틀렸다고 나오더라.

그래서 문제 해설에서 힌트를 얻어서 문제를 해결해 주었다.