백준 2617번: 구슬 찾기 (python)

문제

• https://www.acmicpc.net/problem/2617
• 깊이 우선 탐색을 정점 간 선후 관계 파악에 활용하기

기록 포인트

• 방향 그래프에서 깊이 우선 탐색(DFS)으로 정점의 선후 관계를 파악하는 방법
  • DFS의 탐색 과정에서 각 정점은 본인의 자손보다 먼저 탐색이 종료될 수 없음
  • (위상 정렬에서도 DFS의 이러한 특성을 활용해 전체 정점들을 선후 관계로 정렬함)
  • 그러므로 각 정점의 자손 개수를 확인하면, 전체 정점들을 선후 관계로 정렬(위상 정렬)했을 때의 위치, 즉, '해당 정점 앞에 적어도 몇 개의 정점이 놓이는지' 알 수 있음
  • 가령, 문제 예시를 오름차순으로 바라보면
    • 개별 선후 관계를 정방향 그래프로 표현한 뒤, 정점 1을 시작점으로 DFS을 실행하면 [5,4,2,1] 순으로 탐색이 종료되며 이를 뒤집으면 [1,2,4,5]가 됨
    • 이를 통해 모든 정점을 오름차순으로 정렬 시 정점 1 뒤에 적어도 3개의 정점이 놓인다는 것을 알 수 있음
  • 반대로, 문제 예시를 내림차순으로 바라보면
    • 개별 선후 관계를 역방향 그래프로 표현한 뒤, 정점 1을 시작점으로 DFS를 실행하면 본인만 탐색하고 종료됨
    • 이를 통해 모든 정점을 내림차순으로 정렬 시 정점 1 뒤에 적어도 0개의 정점이 놓인다는 것을 알 수 있음
  • (결과적으로 본 문제는 각 정점의 자손 개수를 확인하는 문제이기 때문에, BFS를 사용해도 상관 없음)
    

접근 방식

• 목표는 특정한 정점이 전체 배열의 정중앙에 위치할 수 있는지 여부를 확인하는 것
  • 전체 배열의 정점 개수는 홀수이므로, 정중앙의 인덱스는 N//2
  • 정중앙에 위치하는 정점을 정확히 알 수는 없으므로, 정중앙에 위치할 수 없는 정점을 찾아야 함
• 특정한 정점(v)이 정중앙에 위치할 수 없는 경우는 아래 2개의 상황임
  • v보다 큰 정점 개수가 N//2개를 넘음 (즉, N//2 + 1 이상)
    • 오름차순으로 정렬 시 v 뒤에 오는 정점의 개수가 N//2 보다 큼
    • 정방향 그래프에서 v를 기준으로 DFS 실행 시 자손의 개수가 N//2 보다 큼
  • 본인보다 작은 정점 개수가 N//2개를 넘음
    • 내림차순으로 정렬 시 v 뒤에 오는 정점의 개수가 N//2 보다 큼
    • 역방향 그래프에서 v를 기준으로 DFS 실행 시 자손의 개수가 N//2 보다 큼

제출 답안

import sys
from collections import defaultdict

N, M = tuple(map(int, sys.stdin.readline().split()))

# 1단계: 정방향 인접 리스트와 역방향 인접 리스트를 각각 생성
adj_f = defaultdict(list) # forward
adj_b = defaultdict(list) # backward
for _ in range(M):
    v1, v2 = tuple(map(int, sys.stdin.readline().split()))
    adj_f[v1].append(v2)
    adj_b[v2].append(v1)

# print(adj_f)
# print(adj_b)

# 2단계: DFS 함수 생성
def DFS_visit(adj, v1, parent, results):
    if v1 in adj:
        for v2 in adj[v1]:
            if v2 not in parent:
                parent[v2] = v1
                DFS_visit(adj, v2, parent, results)
    results.append(v1)

# 3단계: 각 정점을 시작점으로 DFS를 실행했을 때, 해당 정점의 자손 개수를 카운트
answers = set()
for v1 in range(1, N+1):
    # 정방향 그래프 탐색 (오름차순)
    parent, results = {}, []
    parent[v1] = None
    DFS_visit(adj_f, v1, parent, results)
    # print(v1, results)
    # 본인을 제외한 자손들의 수 확인
    # - 본인 제외 자손들의 수가 (N+1)//2 이상이면 본인은 가운데에 올 수 없음
    # - 가령, 구슬이 5개일 때, 자손이 3개 이상이면 본인의 인덱스는 중간인 2보다 커짐
    if len(results)-1 >= (N+1)//2:
        answers.add(v1)
        continue
    # 역방향 그래프 탐색 (내림차순)
    parent, results = {}, []
    parent[v1] = None
    DFS_visit(adj_b, v1, parent, results)
    # print(v1, results)
    if len(results)-1 >= (N+1)//2:
        answers.add(v1)

print(len(answers))