개발해요

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

풀이

문제를 이해하기 위해 예제를 그림으로 그려보았다.

팀을 이루기 위해선 각 학생들이 선택한 학생들을 따라갔을 때, 사이클이 형성되어야 한다는 걸 알 수 있다. 그리고 사이클은 어디서 시작하든지 반드시 생긴다. 사이클이 생기지 않으려면 중간에 화살표가 끊기거나 화살표가 무한히 이어져야 하는데, 그럴려면 팀원을 선택하지 않은 학생이 있거나 학생 수가 무한히 많아야 하기 때문이다.

또한, 2 -> 1 -> 3 -> 3 처럼 중간에 다른 사이클이 생기는 학생이 팀에 속하지 않는 학생이 된다.

그래서 나는 각 학생이 선택한 학생을 배열에 저장한 후, dfs를 사용해서 사이클을 만드는 학생들의 수를 구했다. 그리고 전체 학생 수에서 빼주는 방식으로 답을 구했다.

구현 방식

(1) 모든 학생을 한번씩 시작점으로 탐색해서, 자기 자신으로 돌아오는지 확인

가장 간단해 보이는 건 모든 학생을 시작 지점으로 탐색해서 자기 자신으로 돌아오는지 확인하는 방법인데, 이렇게 하면 시간 초과가 발생한다. 탐색에 걸리는 시간은 O(n), 모든 학생마다 탐색하면 O(n^2) = 100억이 되기 때문이다.

그래서 그래프 탐색에서 시간을 줄이는 방법인, 한번 확인한 학생은 다시 확인하지 않도록 해야 문제를 해결할 수 있다. 

한번 방문했던 학생이 다시 나오면, 이전의 탐색 과정이 그대로 등장한다는 점을 이용한다.

(ex) 1 -> 2  -> 3 -> 1 을 탐색하고 나서, 4 -> 1이 나온다면 1 -> 2 -> 3 -> 1 탐색을 다시 반복하게 된다.)

(2) 중복 체크 자료구조 2개 사용 

확인한 학생은 다시 방문하지 않도록 해야 하는데, 문제는 사이클을 이루는 학생이 다시 나타났을 때 방금 탐색하다가 확인한 건지, 이전 탐색에서 확인한 건지 알 수가 없다는 것이다.

그래서 방문 체크하는 배열을 2개 사용하였다. 

- finished: 사이클을 형성 여부까지 확인했는지 체크

- visited: 한 번이라도 방문 했는지 체크

알고리즘) dfs (재귀 or 스택)

1. 처음 방문하는 학생일 경우 visited에 체크하고 그 학생이 선택한 학생을 방문한다.
2. 다시 방문하는 학생일 경우,
   1. finished가 체크된 학생 -> 이전의 탐색 과정이 그대로 나오므로 탐색을 종료한다.
   2. 그렇지 않다면, 사이클을 형성하는 학생이므로, 그 학생의 다음 학생부터 자기 자신으로 되돌아올 때까지 반복문을 돌리면서 사이클을 형성하는 학생 카운트를 증가시킨다.
3. 함수나 스택을 빠져나가면서 사이클까지 모두 확인했음을 finished에 체크한다.

(3) 방문 확인 배열 + 탐색을 시작할 때마다 새로운 중복 체크 자료구조를 생성해서 사용

탐색 과정에서 이전에 사이클 여부까지 확인했는지를 필터링할 수는 있지만, 새로운 자료구조를 생성할 때마다 O(n)의 시간복잡도가 더 필요해서 결국 O(n^2)으로 시간 초과가 발생한다.

나는 여기서 많이 해맸었다..ㅋㅋ

코드1 (방식 2)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var graph: IntArray
lateinit var visited: BooleanArray
lateinit var finished: BooleanArray
var count = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val answer = StringBuilder()

    repeat(t){
        val n = readLine().toInt()
        val st = StringTokenizer(readLine())
        count = 0
        graph = IntArray(n+1)
        visited = BooleanArray(n+1)
        finished = BooleanArray(n+1)

        for (i in 1..n){
            graph[i] = st.nextToken().toInt()
        }

        for (i in 1..n){
            if (visited[i].not()) dfs(i)
        }

        answer.append(n - count).appendLine()
    }

    print(answer)
}

fun dfs(student: Int){
    // 처음 방문한 학생
    if (visited[student].not()) {
        visited[student] = true // 방문 체크
        dfs(graph[student])     // 다음 학생 방문
    }
    else{
        if (finished[student]) return // 사이클 형성 여부까지 이미 확인한 학생
        else{
            var nextStudent = graph[student] // 자신부터 시작하면 while문이 안돌아간다

            while (nextStudent != student){
                count++ // 사이클을 형성하는 학생 수 증가
                nextStudent = graph[nextStudent]
            }
            count++ // 자기 자신도 센다 ex) 2 -> 1 -> 3 -> 2: 반복문에서 1,3을 세고 마지막에 2를 센다

            return
        }
    }

    finished[student] = true // 사이클 형성 여부까지 확인했음
}

코드2 (방식2와 개념은 같지만 추가 방문 체크용 자료 구조로 Map을 사용했습니다)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var graph: IntArray
lateinit var visited: BooleanArray
lateinit var finished: BooleanArray

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val answer = StringBuilder()

    repeat(t){
        val n = readLine().toInt()
        val st = StringTokenizer(readLine())
        var count = 0
        graph = IntArray(n+1)
        visited = BooleanArray(n+1)
        finished = BooleanArray(n+1)

        for (i in 1..n){
            graph[i] = st.nextToken().toInt()
        }

        for (i in 1..n){
            if (!visited[i]){
                count += dfs(i, mutableListOf(), HashMap<Int, Int>())
                // updateGroup(hasGroup, students, startIndex)
            }
        }

        answer.append(n - count).appendLine()
    }

    print(answer)
}

// Map을 추가 방문 체크 자료구조로 사용했습니다
fun dfs(student: Int, studentList: MutableList<Int>, indexMap: MutableMap<Int, Int>): Int {
    if (finished[student]) return 0 // 사이클 형성 여부가 이미 확인된 학생
    if (visited[student]) {         // 사이클이 형성됨
        return studentList.size - indexMap[student]!!
    }

    visited[student] = true
    indexMap[student] = studentList.size
    studentList.add(student)
    val count = dfs(graph[student], studentList, indexMap)

    finished[student] = true
    return count
}

https://www.acmicpc.net/problem/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)
    }
}