[Swift 알고리즘] 백준 2668 숫자 고르기

안녕하세요 코코종입니다!

오늘은 12시가 넘어서 문제를 올렸네요...

얘랑 너무 오래 싸웠거든요... (feat. 지피티 선생님)

한 구현을 4가지정도로... 해본거 같은데 (원리는 같은데 이상하게 계속 틀리더라구요)

계속 틀려서 으아아아!!!! 하다가 시간을 좀 보내고 집에서 다시 푸는데 아무리 봐도 맞아서 보다보니.... 문제가 마지막 범위에 있었네요 ㅎㅎ... 아으 재밌어...

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/21.
//

import Foundation
// 2668 숫자 고르기 dfs 골5

// idea: key - value로 되어있으니까 처음부터 해서 value를 따라가면서 dfs를 하기?
// dfs가 끝나게 되면 그때 keys 와 values 를 비교해서 같다면 이걸 정답 배열에 추가하기

let n = Int(readLine()!)!
var arr: [Int] = [0]
var answers: [Int] = []

for _ in 0..<n {
    arr.append(Int(readLine()!)!)
}
// key: index, value: arr[index]

func dfs(key: Int, keys: [Int], values: [Int]) { // key: 해당 index, keys: index의 저장, values: value의 저장
    let value = arr[key]
    if keys.contains(key) { // 이미 있는 키라면
        if Set(keys) == Set(values) {
            answers.append(contentsOf: keys)
        }
        return
    }
    
    var values = values
    values.append(value)
    var keys = keys
    keys.append(key)
    
    dfs(key: value, keys: keys, values: values)
}


for i in 1...n { // 여기가 1..<n 이었다는...
    if !answers.contains(i) {
        dfs(key: arr[i], keys: [i], values: [arr[i]])
    }
}

print(answers.count)
answers.sorted().forEach {
    print($0)
}

원리에 대해 설명하자면 각 인덱스 번호 (1~n)을 key로 갖고. 해당 index에 해당하는 값(arr[i])를 value라고 지정했습니다.

이후 해당 key, value를 저장한 배열을 가지고 dfs를 돌아줍니다. 이때 이미 있는 Key의 배열에 속한 key라면 탐색은 멈추고 그때 keys와 values가 같다면(문제에서 주어진 윗줄과 아랫줄이 같다면!) answer에 해당하는 keys(== values)를 append 해줍니다!

쉽게 말하면 순환(cycle)이 발생하는걸 발견하면 그때 비교하고 같다면 순환에 포함된 애들을 다 answer에 더해주는겁니다!

 

p.s 여러분들은 막 80퍼 이런곳에서 틀리면 꼭.... 범위나 엣지케이스를 확인해보세요!!