[Python/파이썬][🥇3] 백준 알고리즘 9466 - 텀 프로젝트

📖[Python/파이썬][🥇3] 백준 알고리즘 9466 - 텀 프로젝트

📜문제

---

💡알고리즘

DFS(깊이우선탐색)

임의의 한 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
#재귀 #순환 #무한루프탈출 #Back-Tracking

---

📕풀이방향

내 포스팅 : [Python/파이썬][🥈1] 백준 알고리즘 14888 - 연산자 끼워넣기
이전 포스팅과 비슷한 DFS알고리즘 + 수열 문제이다.

우선 테스트케이스만큼 실행되므로 하나의 케이스의 동작은 T만큼 반복하는for loof안에서 구현하자
n, number(선택된학생 리스트)를 입력받고, visited(list)와 result(list)를 입력받자
i가 1~n까지 반복하는 for loof에서 visited[i] == False이면 dfs(v)를 실행하자
dfs(v)는 방문처리를 함과 동시에 cycle을 이루는 학생들을 반환해주는 함수로 구현하자

---

📝알고리즘 구현순서

1. n, number(선택된학생 리스트), visited(list), result(list)초기화하고,
   방문 안 한 노드를 dfs(i)로 호출하여 cycle이 되는 학생리스트를 result에 추가하자

---

💻결과코드

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))

---

✏️1. 입력받고, dfs()함수, cycle리스트 구현

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

#cycle 이루는 result 반환
def dfs(v):
    global result      #global이므로 result dfs()밖으로 반환 가능
    visited[v] = True  #방문체크
    cycle.append(v)    #cycle에 v추가
    num = number[v]    #num = v가 선택한 학생

    if visited[num]:   #선택된 학생노드를 방문한 적이 있으면
        if num in cycle:  #dfs()에서 만든 임시cycle에 num이 있는지 확인
            result += cycle[cycle.index(num):]  #result에 임시cycle추가
        return
    else:
        dfs(num)  #선택된 학생노드를 방문한 적잉 없으면 dfs(선택된학생)실행

#테스트 케이스만큼 실행
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 = [] #cycle 초기화 (매 번호마다 팀이 되는 학생이 다르니까)
            dfs(i)

    print(N-len(result))  #팀이 안꾸려진 학생 수 출력

---

📚동작원리 및 정리

❓동작원리

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

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 = []

    for i in range(1,N+1):
        if not visited[i]:
            cycle = []
            dfs(i)

    print(N-len(result))

전 코드를 차례대로 훑어보자
ex)
n = 7
number = 3 1 3 7 3 4 6

for loof부터 살펴보면,
 i = 1
 visited[1] = False이므로 dfs(i)호출
 👉🏻 dfs(1)
    visited[1] = True
    cycle.append(1)     #임시 cycle = [1]
    num = number[1]     #num = 3
    
    if visited[3]:    #방문안했으므로 X
    else dfs(3)
    
 👉🏻 dfs(3)
 	visited[3] = True
    cycle.append(3)     #임시 cycle = [1,3]
    num = number[3]     #num = 3
    
    if visited[3]:    #방문했으므로 O
      if 3 in cycle:    #cycle에 3 있으므로 O
        result = cycle[cycle.index(3):]  #현재 인덱스부터 끝까지 result에 저장
        return
        

❓cycle[cycle.index(3):]만 result에 저장하는 이유

cycle에 [1,3]이 있는데,
1의 number[1] = 3 / 3의 number[3] = 3 이므로
3만 팀을 꾸릴 수 있고, 1은 그 누가 원해도 절대로 팀을 꾸리지 못하기 때문이다.

---

정리

1. list.index(x) : list에서의 x의 인덱스(순서)를 반환한다.