문제 링크
https://www.acmicpc.net/problem/9466
문제 유형
그래프 (DFS)
🌈문제
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.
학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.
예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.
위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.
주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)
2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8출력
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.
3
0💡 아이디어
연결된 cycle을 찾아야 하니, 하나의 노드를 발견하고 그것을 깊이 파고들어야 하는 문제라는 것을 판단하여 DFS로 풀어야 한다는 것을 발견하는 데는 그리 오래 걸리지 않았다. 다만 문제의 조건을 어떻게 재귀 초과 조건을 넘지 않고 푸느냐가 관건이었던 문제라고 생각된다.
조건을 알차게 짜려는 마음에 visited 배열을 만들지 않고 기존 배열을 조작하니까 조건을 하나하나 따지기가 어려웠다.
그리고 인덱스도 0부터 시작하는데 해당 문제는 1부터 시작해기 때문에 인덱스를 임의로 조절해야 하는 필요가 있었다.
재귀함수를 이용하되, visited 배열을 생성하고, cycle을 생성해야 하니까 그를 이용할 수 있는 배열이 존재할 수 있도록 만드는 것이 관건이다.
👨💻 코드 작성
import sys
sys.setrecursionlimit(111111)
def dfs(x):
global result
visited[x] = True
cycle.append(x)
number = students[x]
if visited[number]:
if number in cycle:
result += cycle[cycle.index(number):]
return
else:
dfs(number)
T = int(input())
for _ in range(T):
result = []
n = int(input())
students = [0] + list(map(int, input().split()))
visited = [True] + [False] * n
for i in range(1, n + 1):
if not visited[i]:
cycle = []
dfs(i) #맨 처음엔 dfs(1)
print(n - len(result))dfs 함수를 만들되, result 함수를 이용할 수 있도록 global 선언한다. 이후, 방문한 곳을 하나씩 체크하고 학생이 가지고 있는 지목할 학생을 number로 선언한다. 만약 학생이 체크한 친구가 다른 친구를 체크하였다면 cycle이 존재하는지 확인하고, 존재하지 않는다면 해당 학생은 정답 목록에 추가될 수 없다. 만약 한번도 탐색하지 않은 학생이라면 dfs를 활용하여 연관된 학생을 끝까지 탐색하면 된다.
