[알고리즘] 순열 사이클 (백준 10451번)

10451번: 순열 사이클

 DFS를 이용하여 그래프의 사이클을 찾는 문제다. 사이클 찾는 문제는 꽤 자주 나오지만 막상 풀려고 하면 헷갈린다.

 

Solution

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

import java.util.*

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var count = 0

fun solution() {

    var T = br.readLine().toInt()

    for(t in 0 until T)
    {
        var N = br.readLine().toInt()

        var graph = IntArray(N + 1)
        var strtok = StringTokenizer(br.readLine())

        graph.forEachIndexed { index, i -> if(index > 0) graph[index] = strtok.nextToken().toInt() }

        count = 0
        var visited = BooleanArray(N + 1)

        for(i in 1 .. N)
        {
            if(!visited[i])
                dfs(i, graph, visited, BooleanArray(N + 1))
        }
        bw.write(count.toString())
        bw.newLine()

    }
}

fun dfs(now : Int, graph : IntArray, visited : BooleanArray, now_visited : BooleanArray)
{
    visited[now] = true
    now_visited[now] = true

    var next = graph[now]

    //한번도 방문 안한 경우
    if(!visited[now])
        dfs(now, graph, visited, now_visited)
    else
    {
        //이번 턴에 방문을 한 것이므로 사이클 O
        if(now_visited[next])
            count++
        //이번 턴에 방문을 하지 않은 것이므로 추가적으로 더 검사
        else
            dfs(next, graph, visited, now_visited)
    }
}

fun main() {
    solution()
    br.close()
    bw.close()
}

 그래프 사이클 찾기의 핵심은 DFS를 쓸 때, 전체 방문 여부를 체크하는 visited 배열, 이번 턴에 방문했는지 여부를 체크하는 now_visited 배열을 따로 둬야 하는 것이다.

1. visited가 false면 이번 턴까지 한 번도 방문을 안한 것이니 DFS 재귀 호출을 한다.
2. visited가 true여서 방문했는 적이 있는 노드라면 이번 턴에 방문했는 노드인지, 저번 턴까지 방문한 노드인지 파악해야한다.
   1. now_visited가 true면 이번 턴에 방문한 것이므로 사이클이 성립한다.
   2. now visited가 false이면 이번 턴에 방문하지 않았으므로 visited가 false인 경우와 같이 똑같이 재귀 호출을 한다.