[백준/Python]21276: 계보 복원가 호석

문제

https://www.acmicpc.net/problem/21276
백준 문제집 - 0x1A강 - 위상 정렬

 

알고리즘: 정렬, 해시를 사용한 집합과 맵, 방향 비순환 그래프, 위상 정렬

---

풀이

 

🚨 주의해야할 부분은 후손들이 "직계 조상(=부모)"를 기억하고 있는게 아니라는 것이다.
그냥 본인의 조상 중 아무나를 선택한것이므로, 해당 조상의 범위는 (시조 ~ 부모)인 셈이다.
고로 이 문제를 DFS로 푼다면 조건처리가 까다로워질것이다...(일단 나는 시간초과로 실패함)

 

따라서 BFS로 풀이했는데, 진행 과정은 다음과 같다.

1. 조상 → 자손 형태로 진입차수를 정리해줌
2. 진입차수가 0인 사람들 = 시조 이므로, 시조들을 모두 queue에 삽입
3. 직계자손들을 기록할 리스트를 따로 생성 후 BFS 실행
4. queue가 빌 때까지 아래의 과정을 반복
   • queue에서 노드를 꺼냄
   • 해당 노드의 자손들을 하나씩 순회
     • 자손의 진입차수를 1 감소시킴
     • 감소 후 진입차수가 0이 된다면, 현재 노드의 직계자손이라는 의미.
     • 기록용 리스트에 저장 후 queue에 자손 노드 삽입
5. BFS가 끝나면 시조의 갯수, 정렬된 시조 이름들을 출력
6. 모든 사람의 이름을 정렬 후 사람이름 자식수 자식들...을 한줄씩 출력하면 끝

숫자가 아닌 문자열로 주어지기 때문에 딕셔너리를 활용해야한다.
나는 그냥 (이름→번호), (번호→이름)으로 변환할 수 있게끔 맵핑해줬는데, defaultdict를 사용하는게 더 편할수도...?

취향껏 선택하면 되겠다.

 

전체 코드

# 직계 자손-부모 관계의 노드들만 주어지는게 아님.
# 따라서 DFS로 풀이 시 시간초과가 나온다. 이 문제는 진입차수 + BFS 로 풀어야 통과할 수 있음.

# 메모리: 37136KB / 시간: 496ms
from sys import stdin
from collections import deque


input = stdin.readline

N = int(input())
names = input().rstrip().split()
# 이름과 번호를 매칭시킴
name_to_num = {name: i for i, name in enumerate(names)}  # 1. 이름 -> 번호
num_to_name = {v: k for k, v in name_to_num.items()}  # 2. 번호 -> 이름

graph = [[] for _ in range(N)]
in_degree = [0] * N  # 진입차수가 0인 사람이 시조

M = int(input())
for _ in range(M):
    child, ancester = input().rstrip().split()
    child, ancester = name_to_num[child], name_to_num[ancester]

    graph[ancester].append(child)
    in_degree[child] += 1

# 직계자손들을 기록할 리스트
direct_child = [[] for _ in range(N)]

# 시조들을 큐에 넣고 BFS 실행
root = [i for i in range(N) if in_degree[i] == 0]
queue = deque(root)

# 진입차수로 직계 자손을 계산
def bfs():
    while queue:
        curr = queue.popleft()

        for node in graph[curr]:
            in_degree[node] -= 1
            if in_degree[node] == 0:  # 진입차수가 0이 된다면 현재 노드의 직계자손인셈
                direct_child[curr].append(node)
                queue.append(node)


bfs()
root = [num_to_name[r] for r in root]  # 시조들의 번호를 이름으로 변환

print(len(root))
print(*sorted(root))

for name in sorted(names):
    num = name_to_num[name]
    children = sorted(num_to_name[child] for child in direct_child[num])
    print(name, len(children), *children)

 

그나저나 호석이는 문자열 지옥에도 빠졌다가 계보도 복원했다가 참 바쁘다. 화이팅 호석!