백준 족보 검사하기 [32774] 파이썬(Python) 코드 + 해설

백준 32774 족보 검사하기 문제

백준 32774번 문제는 solved.ac기준 플레티넘 4입니다.

1. 문제 설명

세종이는 자신의 가족 구성원들의 혈액형이 유전적으로 일관성 있게 전달되었는지 궁금해졌다. 가족 구성원의 혈액형과 일부 부모-자식 관계가 주어졌을 때, 모든 혈액형이 유전 규칙에 따라 올바르게 결정될 수 있는지 확인해보려고 한다.

2. 문제 이해하기

1.1 혈액형과 유전형의 관계

• 혈액형은 A형, B형, AB형, O형 중 하나이다.
• 유전형은 AA, AO, BB, BO, AB, OO 중 하나이다.
• 각 유전형에 따른 혈액형은 다음과 같다:
  • AA, AO ⇒ A형
  • BB, BO ⇒ B형
  • AB ⇒ AB형
  • OO ⇒ O형

1.2 부모로부터 자식의 유전형 결정

• 각 부모의 유전형에서 하나씩 알레일(유전자)을 선택한다.
• 선택한 두 알레일을 사전순으로 정렬하여 자식의 유전형을 만든다.
• 예를 들어, 부모의 유전형이 AO와 BO라면, 자식의 가능한 유전형은 AB, AO, BO, OO이다.

1.3 문제의 목표

• 가족 구성원의 혈액형과 일부 부모-자식 관계가 주어진다.
• 모든 구성원의 유전형을 결정하여, 주어진 혈액형이 유전 규칙에 따라 올바르게 나올 수 있는지 확인해야 한다.
• 만약 불가능한 혈액형이 있다면 "Regretful..."을 출력하고, 그렇지 않으면 "Good Family Tree"를 출력한다.

3. 알고리즘 설계

3.1 가능한 유전형의 초기화

• 각 구성원의 혈액형에 따라 가능한 유전형의 집합을 초기화한다.
  • A형 ⇒ {AA, AO}
  • B형 ⇒ {BB, BO}
  • AB형 ⇒ {AB}
  • O형 ⇒ {OO}

3.2 부모-자식 관계 저장

• 각 구성원의 부모와 자식 정보를 저장한다.
• 부모는 최대 한 쌍이며, 부모의 성별은 고려하지 않는다.

3.3 제약 조건 전파 (Constraint Propagation)

• 목표: 가능한 유전형의 집합을 좁혀나가면서 모순이 없는지 확인한다.
• 방법:
  • 큐(queue)를 사용하여 가능한 유전형이 변경된 구성원을 추적한다.
  • BFS(Breadth-First Search) 방식으로 제약 조건을 전파한다.
• 세부 절차:
  1. 초기화:
     • 모든 구성원을 큐에 넣는다.
  2. 반복:
     • 큐에서 구성원을 하나 꺼낸다.
     • 해당 구성원의 가능한 유전형을 기반으로 부모와 자식의 가능한 유전형을 갱신한다.
     • 가능한 유전형이 변경되면, 해당 구성원을 다시 큐에 넣는다.
     • 가능한 유전형이 빈 집합이 되면 "Regretful..."을 출력하고 종료한다.
  3. 종료 조건:
     • 큐가 빌 때까지 반복한다.

3.4. 가능한 유전형 갱신 로직

• 부모로부터 자식의 가능한 유전형 추론:
  • 부모의 가능한 유전형 조합을 통해 자식의 가능한 유전형을 계산한다.
  • 자식의 현재 가능한 유전형과 교집합을 취하여 갱신한다.
• 자식으로부터 부모의 가능한 유전형 추론:
  • 자식의 가능한 유전형과 한 부모의 가능한 유전형을 통해 다른 부모의 가능한 유전형을 추론한다.
  • 부모의 현재 가능한 유전형과 교집합을 취하여 갱신한다.

5.  데이터 구조 설계

4.1 필요한 데이터 구조

• possible_genotypes: 각 구성원의 가능한 유전형 집합 (리스트 형태)
• parents: 각 구성원의 부모 정보 (튜플 형태 또는 None)
• children: 각 구성원의 자식 리스트
• queue: 제약 조건 전파를 위한 큐
• in_queue: 구성원이 큐에 있는지 여부를 나타내는 리스트

4.2 유전형 조합 사전 계산

• parent_to_child: 부모의 유전형 조합으로부터 가능한 자식의 유전형을 계산하여 저장
• child_and_parent_to_other_parent: 자식의 유전형과 한 부모의 유전형으로부터 다른 부모의 가능한 유전형을 계산하여 저장

5. 백준 32774 족보 검사하기 문제 정답 파이썬(python) 코드

import sys
from collections import deque, defaultdict

input = sys.stdin.readline
sys.setrecursionlimit(1 << 25)

# 유전형과 혈액형 매핑
genotype_to_blood = {
    'AA': 'A',
    'AO': 'A',
    'BB': 'B',
    'BO': 'B',
    'AB': 'AB',
    'OO': 'O'
}

# 혈액형과 가능한 유전형 매핑
blood_to_genotype = {
    'A': {'AA', 'AO'},
    'B': {'BB', 'BO'},
    'AB': {'AB'},
    'O': {'OO'}
}

# 부모 유전형 조합으로부터 자식의 가능한 유전형 계산
parent_genotypes = ['AA', 'AO', 'BB', 'BO', 'AB', 'OO']
parent_to_child = {}

for g1 in parent_genotypes:
    for g2 in parent_genotypes:
        possible_children = set()
        for a1 in g1:
            for a2 in g2:
                child_alleles = ''.join(sorted([a1, a2]))
                possible_children.add(child_alleles)
        parent_to_child[(g1, g2)] = possible_children

# 자식의 유전형과 한 부모의 유전형으로부터 다른 부모의 가능한 유전형 계산
child_and_parent_to_other_parent = defaultdict(set)
for (p1_geno, p2_geno), children in parent_to_child.items():
    for child_geno in children:
        child_and_parent_to_other_parent[(child_geno, p1_geno)].add(p2_geno)
        child_and_parent_to_other_parent[(child_geno, p2_geno)].add(p1_geno)

# 입력 받기
N, M = map(int, input().split())
blood_types = [input().strip() for _ in range(N)]

# 각 구성원의 가능한 유전형 초기화
possible_genotypes = [set(blood_to_genotype[blood_types[i]]) for i in range(N)]

# 부모-자식 관계 저장
parents = [None] * N  # 각 구성원의 부모 (p1, p2)
children = [[] for _ in range(N)]  # 각 구성원의 자식 리스트

for _ in range(M):
    a, b, c = map(int, input().split())
    parents[a] = (b, c)
    children[b].append(a)
    children[c].append(a)

# 제약 조건 전파를 위한 큐 초기화
queue = deque()
in_queue = [False] * N

# 모든 구성원을 큐에 추가
for i in range(N):
    queue.append(i)
    in_queue[i] = True

while queue:
    u = queue.popleft()
    in_queue[u] = False

    updated = False

    # 부모로부터 자식의 가능한 유전형 추론
    if parents[u]:
        p1, p2 = parents[u]
        possible_children_genotypes = set()
        for g1 in possible_genotypes[p1]:
            for g2 in possible_genotypes[p2]:
                possible_children_genotypes.update(parent_to_child[(g1, g2)])
        new_possible = possible_genotypes[u] & possible_children_genotypes
        if new_possible != possible_genotypes[u]:
            possible_genotypes[u] = new_possible
            if not possible_genotypes[u]:
                print("Regretful...")
                sys.exit()
            updated = True

    # 자식으로부터 부모의 가능한 유전형 추론
    for child in children[u]:
        other_parent = parents[child][0] if parents[child][1] == u else parents[child][1]
        possible_parents_genotypes = set()
        for child_geno in possible_genotypes[child]:
            for other_parent_geno in possible_genotypes[other_parent]:
                possible_parents_genotypes.update(child_and_parent_to_other_parent[(child_geno, other_parent_geno)])
        new_possible = possible_genotypes[u] & possible_parents_genotypes
        if new_possible != possible_genotypes[u]:
            possible_genotypes[u] = new_possible
            if not possible_genotypes[u]:
                print("Regretful...")
                sys.exit()
            if not in_queue[u]:
                queue.append(u)
                in_queue[u] = True

    # 업데이트가 발생하면, 관련된 부모와 자식들을 큐에 추가
    if updated:
        # 부모의 가능한 유전형이 변경되었을 수 있으므로, 부모를 큐에 추가
        if parents[u]:
            p1, p2 = parents[u]
            if not in_queue[p1]:
                queue.append(p1)
                in_queue[p1] = True
            if not in_queue[p2]:
                queue.append(p2)
                in_queue[p2] = True
        # 자식들을 큐에 추가
        for child in children[u]:
            if not in_queue[child]:
                queue.append(child)
                in_queue[child] = True

print("Good Family Tree")

6. 코드 설명

• 유전형 조합 계산:
  • 부모의 유전형 조합을 통해 가능한 자식의 유전형을 미리 계산하여 parent_to_child 딕셔너리에 저장한다.
  • 자식의 유전형과 한 부모의 유전형으로부터 다른 부모의 가능한 유전형을 child_and_parent_to_other_parent에 저장한다.
• 제약 조건 전파:
  • 큐를 사용하여 BFS 방식으로 가능한 유전형을 전파한다.
  • 부모-자식 관계를 통해 가능한 유전형을 갱신하고, 변경이 발생하면 관련된 구성원을 큐에 추가한다.
• 모순 검사:
  • 가능한 유전형이 빈 집합이 되면 "Regretful..."을 출력하고 프로그램을 종료한다.
  • 모든 과정이 완료되면 "Good Family Tree"를 출력한다.

 

7. 백준 32774 족보 검사하기 제출 결과

백준 32774 족보 검사하기 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다