[백준] [파이썬] [BFS] [DFS] 9466번: 텀 프로젝트

문제 보러 가기

문제

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

학생들이(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까지 번호가 부여된다.)

출력

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

예제 입력 1

2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8

예제 출력 1

3
0

---

BFS문제는 이제 어느정도 유형에 완벽하게 익숙해졌다고 생각했는데 전혀 풀지 못하였다.

이 문제를 여러번 보고 익숙해지자.

우선 검색해보니 대부분의 사람들이 DFS로 풀었었다. 지목한 사람의 지목한 사람의 지목한 사람을 타고 타고 가야하니

DFS가 맞는거 같긴하다. BFS 문제집 모음에서 BFS 문제라고 한건데 좀더 유연하게 문제를 푸는 능력을 갖춰야할 거 같다.

 

DFS 함수를 실행하면 방문 표시를 하고 만든 cycle 리스트에 현재 사람의 번호, 즉 노드를 추가해준다. 

그리고 지목한 다음 사람 노드(next_idx)가 한번도 방문을 안했으면 DFS(next_idx)를 실행해준다, 즉 지목한 사람이 누구를 또 지목했는지 확인한다. 

반대로 지목한 다음 사람(next_idx)이 이미 방문한 상태라면 next_idx가 cycle에 있는지 확인하고 cycle 리스트에 있다면 

cycle 리스트의 지목한 사람의 순서부터 마지막까지 사람들 즉, 사이클을 형성하여 팀을 이룬 사람들을 team 리스트에 넣어준다. 

이때 cycle 리스트를 슬라이싱 하는 이유는 다음과 같다. 

예를 들어 위와 같은 그래프가있다고 했을때, DFS(2)를 실행하면 cycle 리스트에 [2,4,7,6] 이렇게 저장될 것이다. 

여기서 cycle은 4,7,6이므로 cycle이 시작한 4부터 리스트를 잘라주어야한다. 순서는 자연스럽게 정해진다. 

---

DFS로 푼 풀이

import sys 
sys.setrecursionlimit(10**7)

sys.stdin=open('input.txt', 'r')

def DFS(cur_idx):
    global team 
    vis[cur_idx]=True                                     # 방문할때 마다 True 
    cycle.append(cur_idx)
    next_idx=people[cur_idx]                                      # 그 사람이 지목한 사람을 꺼냄 

    if vis[next_idx]:                                    # 지목한 사람이 이미 방문했다면, 즉 Sr이 S1을 지목했을때, 다시 말해 cycle을 형성했을때 
        if next_idx in cycle:                            # 지목한 사람이 cycle에 속해 있다면 
            team += cycle[cycle.index(next_idx):]        # 팀에서 지목한 사람의 위치부터 그 뒤 사람들까지, 즉 cycle이 되는 구간부터 팀을 이룬다
        return 
    else:                                           # 아직 cycle이 완성되지 않았다면 지목한 다음 사람으로 이동 
        DFS(next_idx)

if __name__=="__main__":
    T=int(input())              # 테스트 케이스 
    for _ in range(T):
        N=int(input())          # 사람수 입력 
        people = [0] + list(map(int, input().split())) # 사람들 순서데로 입력받기 
        vis = [False] * (N+1)                       # 사이클 형성 여부를 위해 
        team = [] 

        for idx in range(1, N+1):                     # 사람 idx데로 한번씩 살펴본다 
            if not vis[idx]:                          # 첫 방문일 경우에만 cycle 여부를 확인하면 된다. cycle을 형성하면서 vis를 True로 채워나갈거니깐 
                cycle=[]                            # 한사람씩 첫 방문일때 사이클을 만들어본다
                DFS(idx)                              # 서로 지목한 사람들을 타고 타고 DFS를 반복한다

        print(N-len(team))

---

다음은 BFS로 푼건지 확신이 들지 않는 BFS 방법이다.

import sys 
sys.stdin=open('input.txt','r')

if __name__=="__main__":
    T=int(input()) 
    for _ in range(T):
        N=int(input())
        people = list(map(int, input().split()))
        visited = [False for _ in range(N)]
        cycle = [False for _ in range(N)]

        for idx in range(N):            # N명의 사람을 모두 확인해봄 
            if visited[idx]:            # True이면 즉 이미 방문한 사람이면 
                continue                # 통과 다음을 확인 

            visited[idx]=True           # 현재 사람 방문해서 True로 
            team = [idx]                # 팀을 형성하는지를 확인하기 위해 team에 현재 사람을 넣음 
            cur_idx = idx               # cur_idx를 현재 사람의 idx로 넣음 
            while True:
                next_idx = people[cur_idx]-1        # 현재 사람이 지목한 사람의 idx
                if visited[next_idx]:               # 지목한 사람이 이미 팀형성 확인을 위해서 방문한 적이 있다면 
                    if next_idx not in team:        # team에서 지목한 사람이 있는지 확인, 지목한 사람이 현재 team을 형성하기 위해 cycle을 만드는 중이 아니라면
                        break                       # 없다면 이번 사람(cur_idx)는 팀형성이 안됨
                    else:                           # 지목한 사람이 team에 이미 있다면 
                        j = team.index(next_idx)    # 현재 사람이 지목한 사람의 team 위치 
                        for k in range(j,len(team)):# 지목한 사람이 team에 있고 cycle을 형성해서 지목한 사람부터 team에 속한 사람을 훑으며 cylce을 True로 만든다
                            cycle[team[k]]=True     # 팀이 완성되었으므로 team에 속한 사람들을 cycle에서 True로 만들어줌
                        break                       # 그렇게 cur_idx가 팀을 형성하고 나면 다음 idx를 확인 하기 위해 while문에서 벗어난다

                visited[next_idx]=True              # 현재 사람이 지목한 다음 사람을 확인했으니 방문을 True로 바꿈 
                team.append(next_idx)               # 현재 사람이 지목한 다음 사람을 team에 넣음 
                cur_idx = next_idx                  # 현재 사람이 다음 사람이 됨 -> while문을 반복하며 team을 만듬,
                                                    # 즉 while문 안에 if문을 만들기 전에 지목한 사람의 지목한 사람의 지목한 사람을 계속 team에 넣을 수 있게 반복해야함
                                                    # 그렇다가 Sr이 S1을 선택하여 S1이 이미 방문한 적이 있게 될때 while문에서 빠지며 cycle을 만든다
        print(N-sum(cycle))                         # 다시말해 cycle에서 팀이 형성된 True이 애들을 뺀 값이 팀이 형성되지 않은 사람들의 개수

확실히 BFS방법이 설명이 더 필요하고 DFS가 더 직관적이다. 그래서 다들 DFS로 풀었나보다.