[백준] [파이썬] [DP] [위상정렬] 21276번: 계보 복원가 호석

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

21276번: 계보 복원가 호석 문제보기

 

제한시간: 1초
메모리 제한: 512 MB

문제

석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다.

그러던 어느 날, 유구한 역사를 지닌 석호촌의 도서관에 화재가 나서 계보들이 모두 불타고 말았다. 그래도 계보는 있어야 하지 않겠느냐는 마을 어르신인 대일 촌장님의 의견에 따라 석호촌 사람들은 계보 복원가 호석에게 의뢰를 맡기기로 했다.

적어도 현재를 함께 살아가는 N 명의 계보는 복원하고 싶은 호석이는 조사를 통해서 각자가 기억하는 조상들의 이름들을 구해냈다. 다행히도 석호촌의 맑은 정기 덕분에 기억력이 굉장히 좋은 주민들은 모든 조상을 완벽하게 기억하고 있다. 또한, 각 가문은 한 명의 시조를 root로 하는 트리 형태를 띈다는 것도 알아냈다. 이 때 "조상"이란, "자신의 부모"와 "부모의 조상"을 모두 합친 것을 의미한다.

이를 기반으로 몇 개의 가문이 존재했는 지, 각 가문에 대한 정보를 출력하는 프로그램을 작성해서 호석이를 도와주자!

입력

첫번째 줄에 석호촌에 살고 있는 사람의 수 N 이 주어진다. 두번째 줄에는 현재 살고 있는 사람들의 이름이 차례대로 주어진다. 모든 이름은 길이 1 이상 6 이하의 알파벳 소문자로 이뤄지며, 중복된 이름은 존재하지 않는다.

세번째 줄에는 기억하는 정보의 개수 M 이 주어진다. 이어지는 M개의 줄에는 "X Y" 꼴로 기억들이 주어지는데, 이는 곧 X의 조상 중에 Y가 있다는 것을 의미하며 같은 정보가 중복되어 주어지지 않는다. 입력에 모순이 있는 경우는 주어지지 않는다.

출력

첫번째 줄에는 가문의 개수 K 를 출력하라. 두 번째 줄에는 각 가문의 시조들의 이름을 공백으로 구분하여 사전순으로 출력하라.

세번째 줄부터는 이름의 사전순 대로 사람의 이름과 자식의 수, 그리고 사전순으로 자식들의 이름을 공백으로 구분하여 출력하라.

제한

• 1 ≤ N ≤ 1,000
• 0 ≤ M ≤ N×(N-1)/2

예제 입력 1

7
daeil sangdo yuri hoseok minji doha haeun
7
hoseok sangdo
yuri minji
hoseok daeil
daeil sangdo
haeun doha
doha minji
haeun minji
7

예제 출력 1

2
minji sangdo
daeil 1 hoseok
doha 1 haeun
haeun 0
hoseok 0
minji 2 doha yuri
sangdo 1 daeil
yuri 0

 

---

기존의 위상정렬문제들을 패턴화하여 위상정렬스럽게 풀었다. 위상정렬문제들 보기--> 위상정렬문제들

 

그러나 부분 정답이 되었다. 또 이런 경우는 처음이네 

 

가장 후손부터 한세대씩 올라가면서 보는 방식으로 하였는데 부분 정답만 맞고 도저히 해결을 못하였다. 

 

블로그 검색을 통해 얻은 힌트는 가장 조상, 즉 가문의 시조부터 한세대씩 내려가야하는 것 같다. 

---

부분 정답 코드, 가장 후손부터 윗세대로 

import sys 
from collections import deque

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

input=sys.stdin.readline


if __name__=="__main__":
    N=int(input())                              # 사람의 수 
    people=sorted(list(map(str, input().split())))      # 사람들 이름 
    # people = ['daeil', 'doha', 'haeun', 'hoseok', 'minji', 'sangdo', 'yuri']
    people_info={}
    for i,p in enumerate(people):
        people_info[p]=i+1
    # people_info = {'daeil': 1, 'doha': 2, 'haeun': 3, 'hoseok': 4, 'minji': 5, 'sangdo': 6, 'yuri': 7}
    M=int(input())                              # 기억하는 정보의 개수 
    
    graph=[[] for _ in range(N+1)]              # 사람들 이름을 index로 하여 정보를 저장할 그래프 생성
    arr=[0]*(N+1)                               # 사람들 진입차수/우선순위 표기 
    for _ in range(M):
        x,y=map(str, input().split())           # x의 조상 중에 y가 있음    
        graph[people_info[x]].append(people_info[y])    # x 자식 위치에 y 조상을 넣음 
        arr[people_info[y]]+=1                  # y조상이 갖는 자손 수 카운트, arr[?]가 0인 ?는 가장 후손
    
    res=[[] for _ in range(N+1)] 
    ans=[]
    Q=deque()
    for i in range(1,N+1):
        if not graph[i]:            # 부모가 없는 경우가 가문의 조상임 
            ans.append(people[i-1])
        if arr[i]==0:                   # 우선순위가 높은,진입차수가 낮은 가장 후손을 큐에 넣음 
            Q.append(i)
    
    # 가장 후손들 부터 살펴보며 윗세대로 올라간다
    while Q:
        x=Q.popleft()
        if len(graph[x])==1:                        # 내 위로 한분 밖에 안계실때 
            res[graph[x][0]].append(people[x-1])    # 내 윗분의 자손 리스트에 나를 넣음
        else:
            for p in graph[x]:                      # 내(x) 조상들 살펴봄
                arr[p]-=1
                if arr[p]==0:                       # x에 대해 arr[p]가 0이 되었다 -> 내(x) 한세대 위(p)
                    res[p].append(people[x-1])      # 한세대 위 p에 나(x)를 넣음 
                    Q.append(p)                     # 바로 윗세대 p를 큐에 넣어줌 
    
    print(len(ans))
    print(*ans)
    for i in range(1,N+1):
        print(people[i-1], len(res[i]), *sorted(res[i]))

---

정답 코드 

import sys
from collections import deque

input = sys.stdin.readline

if __name__=="__main__":
    # 사람들의 수
    N=int(input())

    # 사람들의 이름
    people=sorted(list(map(str, input().split())))
    people_info={}  
    # {'daeil': 1, 'doha': 2, 'haeun': 3, 'hoseok': 4, 'minji': 5, 'sangdo': 6, 'yuri': 7}
    for i,p in enumerate(people):
        people_info[p]=i+1

    # 기억하는 정보의 개수 
    M=int(input())

    parents=[[] for _ in range(N+1)]    # 사람들 이름을 index로 하여 정보를 저장할 그래프 생성
    childs=[[] for _ in range(N+1)] 
    indegree=[0]*(N+1)
    for _ in range(M):
        c,p=map(str, input().split())
        # 자식의 부모를 저장
        parents[people_info[c]].append(people_info[p])
        # 부모의 자식을 저장
        childs[people_info[p]].append(people_info[c])
        # child를 가르키고 있는 조상의 수
        indegree[people_info[c]] += 1

    # 가문의 시조
    Q=deque()
    roots=[]
    res=[[] for _ in range(N+1)] 
    for p in range(1,N+1):
        # 부모가 없는 경우가 가문의 조상이다.
        if not parents[p]:
            Q.append(p)
            roots.append(people[p-1])

    # 조상의 수 출력
    print(len(roots))
    # 조상들 출력
    print(*roots)
    
    # 가문의 시조를 시작으로 내려가면서 자손들을 살펴본다
    while Q:
        x = Q.popleft()
        for child in childs[x]:     # 나(x)의 자손을 살펴봄 
            indegree[child] -= 1    # x의 자손들중 하나의 자손(child)의 조상 수를 하나 지움
            # indegree가 0으로 만드는 부모가 직계 부모이다.
            if indegree[child] == 0:        # x에 대해 indegree[child]가 0이 되었다 -> 내(x) 한세대 아래(child)
                res[x].append(people[child-1])  # x 위치에 한세대 아래 child를 넣음 
                Q.append(child)                 # 바로 아랫세대인 child를 큐에 넣어줌 

    
    for i in range(1,N+1):
        print(people[i-1], len(res[i]), *sorted(res[i]))

 

참... 위상정렬 패턴화는 되었는데 디테일이나 까다로운거는 계속 틀리는거 같다....