[알고리즘] 백준 9466 텀프로젝트 [python, swift]

텀 프로젝트 성공다국어

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

3 초

256 MB

67837

17198

11585

23.963%

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1234567

3

1

3

7

3

4

6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

 

 

 

해결방법

dfs로 돌다가, 이전에 간 적이 있는 ind 를 만날 경우에 분기를 합니다. 여태까지 움직였던 정점들을 prev에 담고, visited[cur] 이 True인 경우에 두가지 케이스로 나뉩니다.

1. 과거 dfs탐색 (for 문에서 0...n 까지 dfs를 돕니다. 그 때 과거에 이미 방문한 경험이 있는 경우 )

  이 경우에는 과거 탐색이기 때문에 현재 prev배열에 존재하지 않습니다. 그냥 Return 해 줍ㄴ디ㅏ.

2. 현재 dfs탐색(for 문에서 0...n 까지 dfs를 돌때 현재 ind에서 파생된 경우)

  명확하게 prev배열에 cur이 존재하기 때문에 사이클에 관한 값을 res에 보정해 줍니다.

 

 

 

 

import Foundation

func sol() -> String {
    let n = Int(readLine()!)!
    let arrs = readLine()!.split(separator: " ").map{Int($0)! - 1}
    var prev: [Int] = []
    var visited = Array(repeating: false, count: n)
    var res = 0

    func dfs(_ cur: Int) {
        if visited[cur] == true {
            if prev.contains(cur) {
                res += prev[prev.firstIndex(of: cur)!...].count
            }
            return 
        }

        visited[cur] = true
        prev.append(cur)
        dfs(arrs[cur])
    }

    for i in 0..<n {
        if visited[i] == false {
            prev = []
            dfs(i)
        }
    }
    return "\(n - res)"
}

let result = (0..<Int(readLine()!)!).map{ _ in
    return sol()
}
print(result.joined(separator: "\n"))

 

 

import sys
sys.setrecursionlimit(150000)

def sol() :
    n = int(sys.stdin.readline())
    arrs = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
    visited = [False] * n
    prev = []
    res = 0
    def dfs(cur: int) :
        nonlocal visited, res
        if visited[cur] == True:
            if cur in prev :
                res += len(prev[prev.index(cur):]) 
            return
        else :
            visited[cur] = True
            prev.append(cur)
            dfs(arrs[cur])
    
    for ind in range(n):
        if visited[ind] == False:
            prev = []
            dfs(ind)
    print(n - res)
    
list(map(lambda _: sol(), range(int(input()))))