[백준/Python]9466: 텀 프로젝트

문제

https://www.acmicpc.net/problem/9466
백준 문제집 - BOJ 길라잡이 베타 (1)

알고리즘: DFS

---

풀이

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

 

처음엔 유니온 파인드를 사용해야하나? 싶었고 구상해봤으나 실패...
알고보니 DFS(깊이우선탐색) 문제였다.

 

1번이 2번을 선택하고, 2번이 3번을 선택하고, 3번이 1번을 선택하면 이 셋은 한 팀이다.
따라서 이 문제는 그래프에서 사이클의 갯수를 찾는것과 동일하다.

 

각 번호의 방문여부를 저장할 visited를 생성해주고(편의상 n+1개로)
하나씩 순회하며 방문하지 않은 순번일경우 DFS를 실행한다.

 

DFS를 통해 '팀을 가진 사람들'의 수를 구하는것이다.

 

DFS는 실행될때마다 빈 리스트를 생성하는데, 여기엔 현재 순번부터 앞으로 선택될 순번들을 저장해준다.
(현재 순번을 A1, 다음 순번을 An이라 한다면 A1 -> A2 -> A3 ...)

 

만약, 다음 순번이 이미 방문처리된 상태고 리스트에 존재한다면 사이클(팀)이라는 소리이므로,
리스트의 길이 - 이미 들어있는 순번의 인덱스값을 반환한다.

하지만 방문처리만 되어있고 리스트에는 없는 상태라면 완전히 따로국밥인 상태이니 0을 반환해준다.

 

그 외 방문하지 않은 순번에 한해선 방문처리, 리스트 추가, 다음 순번 지정 을 실행한다.

 

모든 순번이 방문처리되면 전체 인원 수 - 팀을 가진 사람들의 값을 출력한다.

 

전체코드

# 메모리: 48104KB / 시간: 2116ms
from sys import stdin


input = stdin.readline

def dfs(start):
    global teams

    team = [start]
    visited[start] = True
    nxt = lst[start]

    while True:
        if visited[nxt]:
            if nxt in team:  # 방문한 상태이고 team에 존재한다면,
                return len(team) - team.index(nxt)  # team 길이 - nxt의 첫번째 위치 반환
            else:
                return 0
        else:
            visited[nxt] = True
            team.append(nxt)
            nxt = lst[nxt]

for _ in range(int(input())):
    n = int(input())
    lst = [0] + list(map(int, input().split()))
    visited = [False] * (n+1)

    teams = 0

    for i in range(1, n+1):
        if not visited[i]:
            teams += dfs(i)
    print(n - teams)

---

다른 풀이들을 찾아보니 다들 재귀로 푸는 듯하다...
아래는 재귀를 사용한 풀이인데 가독성 측면에선 이게 더 나은것같다.

# 출처👉 https://velog.io/@keynene/Python%ED%8C%8C%EC%9D%B4%EC%8D%AC3-%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-9466-%ED%85%80-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

#cycle 이루는 result 반환
def dfs(v):
    global result
    visited[v] = True
    cycle.append(v)
    num = number[v]

    if visited[num]:
        if num in cycle:
            result += cycle[cycle.index(num):]
        return
    else:
        dfs(num)

#테스트 케이스만큼 실행
for _ in range(int(input().rstrip())):
    N = int(input().rstrip())
    number = [0] + list(map(int, input().split()))
    visited = [True] + [False]*N
    result = []

    #1~n까지 방문여부 확인하면서 dfs()호출
    for i in range(1,N+1):
        if not visited[i]:
            cycle = []
            dfs(i)

    print(N-len(result))