[백준/BOJ] 10451번: 순열 사이클

문제

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

10451번: 순열 사이클

해설

위 그림은 예제 입력의 첫 번째 테스트케이스이다.

색을 맞춰보면

case1.          case2.          case3

1 → 3           2 → 2           4 → 8

3 → 7                                8 → 6

7 → 5                                6 → 4

5 → 1

이처럼 3가지의 순환 사이클로 나뉘는 것을 확인할 수 있다.

 

이를 구현하는 방법을 알아보자.

나의 경우 Map에 인덱스와 값을 저장하고, 재귀를 통해 구현하였다.

Map의 key에는 1부터 n까지의 수를 저장하고, value에는 입력한 값을 순서대로 저장한다.

이를 통해 몇 번재 인덱스에 어떠한 값이 있는지 알 수 있게 된다.

 

이미 방문한 칸은 다시 방문할 필요가 없기 때문에 방문 여부를 처리할 배열이 필요하다.

따라서 n의 크기를 가진 Boolean 배열을 선언한다.

 

필요한 변수는 모두 준비되었다.

1부터 n까지 반복을 하며 아직 방문하지 않은 칸이라면 새로운 순환 사이클을 찾은 것이므로 cnt를 증가시켜준다.

현재 노드를 방문 체크를 해주면서, 이와 연결된 칸(order[curNode] 즉, value)이 이미 방문한 칸인지 확인해준다.

이미 방문한 칸일 경우, 이 순환 사이클은 끝나게 된다.

아직 방문하지 않은 칸이라면, 방문한 칸이 나올 때까지 재귀 함수를 수행해주면 된다.

 

n까지의 반복이 끝났을 때, 최종적으로 몇 개의 순환 사이클이 있는지 구할 수 있다.

코드

private lateinit var visited: BooleanArray
private val order = mutableMapOf<Int, Int>()
private var cnt = 0

fun main() = with(System.`in`.bufferedReader()) {
    repeat(readLine().toInt()) {
        cnt = 0
        val n = readLine().toInt()
        val arr = readLine().split(" ").map { it.toInt() }

        visited = BooleanArray(n+1)

        arr.forEachIndexed { index, i ->
            order[index + 1] = i
        }

        (1..n).forEach { i ->
            if(!visited[i]) {
                cnt++
                checkLink(i)
            }
        }

        println(cnt)
    }
}

private fun checkLink(curNode: Int) {
    visited[curNode] = true
    val nextNode = order[curNode]

    if(!visited[nextNode!!]) checkLink(nextNode)
}

추가

문제를 푼 후 깨달은 것인데, 굳이 Map을 이용할 필요가 없었다.

배열을 이용하는데, 배열의 index는 0부터 시작이므로 입력받은 모든 값들에 -1을 하여 문제를 풀어도 되겠다는 생각이 들었다.

즉 다음과 같은 코드가 된다.

private lateinit var visited: BooleanArray
private lateinit var arr: IntArray
private var cnt = 0

fun main() = with(System.`in`.bufferedReader()) {
    repeat(readLine().toInt()) {
        cnt = 0
        val n = readLine().toInt()

        val input = readLine().split(" ").map { it.toInt() - 1 }
        arr = IntArray(n) {  input[it] }
        visited = BooleanArray(n)


        arr.forEachIndexed { index, i ->
            if(!visited[index]) {
                cnt++
                checkLink(i)
            }
        }

        println(cnt)
    }
}

private fun checkLink(curNode: Int) {
    visited[curNode] = true
    val nextNode = arr[curNode]

    if(!visited[nextNode!!]) checkLink(nextNode)
}

n까지 반복을 하며 Map에 저장하는 과정이 빠져서인지 메모리와 시간이 많이 줄어든 것을 확인할 수 있었다.