백준 2668번: 숫자고르기 (Kotlin)

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

2668번: 숫자고르기

 

풀이 & 잡담

어떤 알고리즘을 써야할까 고민을 많이 했다. 정렬, 그리디, 백트래킹, ... 그래프 탐색? 예시를 보니까 (1번 - 3번)을 고르면 3번을 타고 들어가서 (3번 -1번)을 고르는 식으로, 왠지 그래프 탐색 아닐까 생각이 들었다. 하지만 풀이 방법이 확실하게 떠오르지 않았고 알고리즘 유형을 봤더니 dfs 문제였는데, 그걸로 어떻게 최대 개수로 같은 집합을 뽑게 만들라는 건지 여전히 감이 오지 않았다. 그래서 풀이 방법을 찾아봤는데, dfs를 통해 그래프 방문의 사이클을 찾아내는 문제였다.

 

사이클은 반드시 형성된다. 아랫줄의 번호들이 1~n이기 때문이다. 같은 숫자가 2번 나오든, n까지 하나씩 나오든 반드시 사이클이 형성되므로, 사이클을 형성하는 번호들을 모두 찾으면 그것이 답이다.

 

사실 이 문제 이해하려고 다른 사람들 코드도 많이 보고, 생각을 많이 했더니 뭐가 이해가 안됐는지 기억이 안난다. 내가 뭘 모르는지 아는 것도 어려운 거였다.

 

쓰리디핏님의 블로그(https://3dpit.tistory.com/12)를 참고했는데, 접근 방법을 보며 금방 이해할 수 있었다. 그리고 사실 약간 충격을 받았다, 내가 여태껏 수동적으로 문제를 풀고 있었구나... 앞으론 이해가 잘 안될 때는 직접 그림도 그려보고, 예시를 적극적으로 활용하면서 문제를 이해해봐야겠다고 반성했다. 

 

사이클을 발견하는 문제란 건 알았는데, 어떻게 구현하는지도 문제였다. 가장 간결한 방법은 첫번째 줄에 있는 숫자들을 기준으로 1~n까지 하나씩 그래프 탐색을 하면서 (ex: 1을 시작으로 방문 -> 1은 3과 연결되어 있으므로 1을 방문 체크하고 3을 방문, 3을 방문 체크하고 연결되어 있는 1을 방문 ....) 사이클을 형성하는지 확인하는 것이다. 사이클은 반드시 형성되므로, 첫째줄에 있는 숫자들을 기준으로 방문 여부를 체크해서 중복 방문할 때 시작 번호에서 사이클이 형성되는지 확인하면 된다.

코드1이 이런 방식이다.

코드2는 위, 아래 줄의 방문한 번호들을 다 저장해가면서 푸는, 좀 더 직관에 가까운 풀이법이고,

코드3는 dfs는 스택으로도 풀 수 있을테니 시도해보다가, 단순하게 변수만 사용해도 구현이 가능하길래 변수로 스택을 사용한 것처럼 구현했다. 채점해보니 재귀보다 느렸다

 

이번 문제는 어렵게 느껴저서, 여러 코드를 읽어봤다. 복습에도, 문제 해결에 관한 사고력을 늘리는 데에도 도움이 많이 될 것 같아서 앞으로도 잘 안풀리는 문제들은 이렇게 공부하려고 한다.

 

코드1

fun main() {
    val n = readLine()!!.toInt()
    val secondLine = IntArray(n+1)
    val answerList = mutableListOf<Int>()

    repeat(n){ i ->
        secondLine[i+1] = readLine()!!.toInt()
    }

	// 첫째 쭐의 번호들을 대상으로 사이클을 형성하는 숫자인지 확인한다.
    for (i in 1..n){
        val visited = Array(n+1){ false }.apply{ this[i] = true }
        if(hasCycle(i, secondLine[i], visited, secondLine)){
            answerList.add(i)
        }
    }

    // 1부터 사이클을 확인했으므로 정렬하지 않아도 된다
    println(answerList.size)
    answerList.forEach{
        println(it)
    }
}

fun hasCycle(start: Int, current: Int, visited: Array<Boolean>, secondLine: IntArray): Boolean {
    // 현재 번호를 처음 방문하는 거라면 방문 처리를 하고 연결된 다음 번호를 방문한다
    if (visited[current].not()){
        visited[current] = true
        return hasCycle(start, secondLine[current], visited, secondLine)
    }

    // 중복 방문일 때, 탐색을 시작한 번호에서 사이클 시작된다 -> 사이클을 형성하는 번호(정답)이다
    // 중간에 사이클이 형성된다 -> 정답이 아니다
    return start == current
}

 

코드2

val answerList = mutableListOf<Int>()

fun main() {
    val n = readLine()!!.toInt()
    val secondLine = IntArray(n + 1)
    val isAnswer = Array(n + 1) { false }

    repeat(n) { i ->
        secondLine[i + 1] = readLine()!!.trim().toInt()
    }

    for (i in 1..n) {
        if (isAnswer[i]) continue

        val visitedFirstLine = mutableSetOf<Int>()
        val visitedSecondLine = mutableSetOf<Int>()
        checkCycle(i, secondLine, visitedFirstLine, visitedSecondLine, isAnswer)
    }

    println(answerList.size)
    answerList.sorted().forEach {
        println(it)
    }
}

fun checkCycle(
    index: Int,
    secondLine: IntArray,
    visitedFirstLine: MutableSet<Int>,
    visitedSecondLine: MutableSet<Int>,
    isAnswer: Array<Boolean>
){
    if (visitedFirstLine.contains(index)) {
        return
    }

    visitedFirstLine.add(index)
    visitedSecondLine.add(secondLine[index])
    if (visitedFirstLine == visitedSecondLine){
        visitedFirstLine.forEach { i ->
            isAnswer[i] = true
            answerList.add(i)
        }
        return
    }

    checkCycle(secondLine[index], secondLine, visitedFirstLine, visitedSecondLine, isAnswer)
}

 

코드3

fun main() {
    val n = readLine()!!.toInt()
    val secondLine = IntArray(n + 1)
    val answerList = mutableListOf<Int>()


    repeat(n) { i ->
        secondLine[i + 1] = readLine()!!.trim().toInt()
    }

    for (startIndex in 1..n) {
        val visited = Array(n + 1) { false }.apply { this[startIndex] = true }
        var currentIndex = secondLine[startIndex]

        while (true) {

            if (!visited[currentIndex]) {
                visited[currentIndex] = true
                currentIndex = secondLine[currentIndex]
                continue
            }
            
            if (startIndex == currentIndex) {
                answerList.add(startIndex)
            }
            break
        }
    }

    println(answerList.size)
    answerList.forEach {
        println(it)
    }
}