백준 2617 구슬찾기 (DFS 파이썬)

예쁜 구슬

https://www.acmicpc.net/problem/2617

2617번: 구슬 찾기

풀때는 어려웠는데, 막상 풀고 다시 살펴보니 DFS로 접근하는 것이 매우 적합 한 것 같다.

문제의 핵심

• 문제에 주어진 연결관계를 통하여 특정 구슬(노드)의 하부 트리에 속하는 노드 숫자 구하기. (DFS)
  이때 '더 큰 구슬의 그룹', '더 작은 구슬의 그룹'으로 나눈 후에 루트가 '더 큰 그래프 구조'로 한번 탐색하고, '더 작은 그래프 구조'로 각각 한번씩 탐색한다. 이를 통해 특정 구슬보다 더 큰 구슬의 개수, 혹은 더 작은 구슬의 개수를 계산한다.
• 더 큰 구슬의 개수 혹은 더 작은 구슬의 개수가 중간값인 (N+1)/2를 넘어가면 적어도 중간값은 될  수 없음을 판단할 수 있다. 

특정 구슬보다 작은경우, 큰 경우 

재귀함수를 이용한 DFS / 스택을 이용한 DFS 두 가지 풀이로 풀어보았다.

1. 스택 이용한  DFS

## DFS with stack
import sys
from collections import deque
input=sys.stdin.readline

N, M =map(int,input().split())

bigger_lst=[[] for _ in range(N+1)]  # index보다 큰 수
smaller_lst=[[] for _ in range(N+1)]  # index보다 작은 수
mid=(N+1)/2 #개수 기준 중간값

for i in range(M):  #값 입력후 배열
    a,b=map(int,input().split())
    bigger_lst[b].append(a)
    smaller_lst[a].append(b)

def dfs(arr, start):
    cnt=0
    visited[start]=True
    stack=deque()
    stack.append(start)
    while stack:
        x=stack.popleft()
        for i in arr[x]:
            if not visited[i]:
                cnt+=1
                visited[i]=True
                stack.append(i)
    return cnt
    
answer=0
for i in range(1,N+1):
    visited=[False]*(N+1)
    if dfs(bigger_lst,i)>=mid:
        answer+=1
    if dfs(smaller_lst,i)>=mid:
        answer+=1
print(answer)

2. 재귀함수를 이용한  DFS

#DFS with recursion
import sys
from collections import deque
input=sys.stdin.readline

N, M =map(int,input().split())

bigger_lst=[[] for _ in range(N+1)]  # index보다 큰 수
smaller_lst=[[] for _ in range(N+1)]  # index보다 작은 수
mid=(N+1)/2 #개수 기준 중간값

for i in range(M):  #값 입력후 배열
    a,b=map(int,input().split())
    bigger_lst[b].append(a)
    smaller_lst[a].append(b)

def dfs(arr, n): (재귀)   #bigger, smaller, list보고 n보다 크거나 작은 숫자 개수 파악
    global cnt
    for i in arr[n]:
        if not visited[i]:
            visited[i]=True
            cnt+=1
            dfs(arr,i)

answer=0
for i in range(1,N+1):
    visited=[False]*(N+1)
    cnt=0
    dfs(bigger_lst,i)
    if cnt>=mid:
        answer+=1
    cnt=0
    dfs(smaller_lst,i)
    if cnt>=mid:
        answer+=1

print(answer)