https://www.acmicpc.net/problem/3499
시간 1초, 메모리 128MB
input :
- n (1 ≤ n ≤ 100,000)
- n개의 개체의 성별
- m (0 ≤ m ≤ 100,000)
- 새로운 개체 : 아빠 ID, 엄마 ID, 성별
- 죽은 개체 : -(본인 ID)
- k (0 ≤ k ≤ n + m)
- ID, 식별번호
output :
- YES : 실험이 끝났을 때 생존한 개체가 모두 같은 미토콘드리아 DNA를 가지는 경우.
- NO : 실험이 끝났을 때 생존한 어떤 개체들이 서로 다른 미토콘드리아 DNA를 가지는 경우.
- POSSIBLY : YES와 NO를 확정할 수 없는 경우.
조건 :
-
창영이는 메모장에 '.', '\', '/'을 이용해서 도형을 그렸다.
-
1*1크기의 단위 정사각형을 나타낸다.
위의 사이트에서 테케를 받아서 해결한다면 훨씬 수월하다.
예제 1에 대한 그래프
이 상태에서 1, 2, 3, 4, 6, 7을 제외한 후 식별이 가능한지 판단 하면 된다.
결과
동일한 모계를 가지고 있어 식별번호가 동일하다고 볼 수 있다.
예제 2에 대한 그래프
.png)
이 상태에서 3을 제외한 후 식별이 가능한지 판단 하면 된다.
결과
동일한 식별번호로 Update된다. 자식에 의해 부모의 식별번호를 알 수 있다.
예제 3에 대한 그래프
.png)
결과
동일한 모계 + 식별번호를 모름. 이를 통해 POSSIBLY를 출력해야 하는 경우.
예제 4에 대한 그래프
결과
식별 번호 자체가 다름. NO를 출력
사고
초반 30분 동안은 문제 해석을 위해 사용했고 그 이후에는 정확한 가이드 라인이 없이 해서 시간을 많이 소요했다. 생각 한 후에 세운 가이드 라인은 이러 했다.
- Female에 대한 graph 생성 (식별 ID check를 BFS로 수행)
- node에 대한 parent 저장(식별 ID 업데이트를 위함)
- dead node 저장(마지막에 제외를 하고 ID를 체크)
- M, F의 식별번호를 나누어 set으로 체킹
추가 상황
마지막 체킹을 하는 것이 제일 중요하다.
1. 식별 번호가 없는 경우
=> 이를 체킹하기 위해 음수의 인덱싱을 하였다. 식별번호는 언제나 양수라서 음수 인덱싱으로 부모를 따라가게 하였다.
2. 부모들이 다른 경우
=> 이 경우 POSSIBLY, NO 둘 중 하나인데 NO가 되려면 식별번호가 있어야 한다. 2개 이상의 집단의 식별 번호가 양수여야 한다.
3. 식별번호가 있는 경우
=> 여기서는 YES, POSSIBLY를 나누면 될 것이다. 식별번호가 1개만 있는 경우에 set의 길이가 1이면 YES이고 그렇지 않으면 POSSIBLY가 된다.
다음 풀이
- 모계 조상은 가계도의 여성 부분을 타고 거슬러 올라가면 나오는 조상이다.
- 출생은 세 단어로 주어지는데, 순서대로 아빠의 ID, 엄마의 ID, 성별
- 전자는 미토콘드리아 DNA가 분석된 개체의 ID이고, 후자는 그 개체의 미토콘드리아 DNA의 고유 식별 번호이다.
본인이 유도를 해야 하는 부분이 아주 조금 있다. 1번에 의해 3번의 결과를 자신의 부모, 자식에 대해 모두 업데이트를 수행해야 한다. 이를 위한 방식을 위에 적어둔 방식을 사용해야 함을 빠르게 생각해야 겠다.
마지막 결과 출력하는 방식은 set과 같이 Unique한 값을 가지게 하는 자료구조를 사용해야 한다. 두 부분으로 나눠서 하는 부분이 편리할 것 같다.
추가
파일 오픈을 사용해서 개인적인 테스트를 사용할 수 있다.
백준에 코드 제출 시에는 sys.stdin.readline()를 사용하지만 이를
f = open("test case path", "r")
f.readline()로 변경 하여 사용할 수 있다. 물론 sys.stdin을 모두 f로 바꿔야 한다.
for i in range(1, 54):
num = str(i)
if i < 10:
num = f"0{num}"
url = f"file Path your own\\{num}"
f = open(url, "r")
answer = open(url + ".a", "r").readline().rstrip()
# add your code
gonna = None
print(f"실제 {i}번째 테케 : {answer}")
print(gonna)
if answer != gonna:
break
이를 통해 예외적인 케이스를 체크 할 수 있다.
> 사실 테케가 없었으면 못 풀지 않았을까 싶다. f_temp에서 식별번호가 없는 경우를 생각하지 않는 바람에 틀렸다. 다음에는 체크해야 하는 집단이 2개라면 모두 동일하게 체크를 해야겠다.
import sys
from collections import deque
def find(node, value):
if node == parent[node]:
return
ids[parent[node]] = value
find(parent[node], value)
def bfs(ins_id):
q = deque([ins_id])
while q:
node = q.popleft()
if node not in graph:
continue
for next_node in graph[node]:
ids[next_node] = ids[ins_id]
q.append(next_node)
n = int(sys.stdin.readline())
# ids는 실제 개체의 식별 번호를 저장하기 위함.
# graph에는 이미 죽은 개체가 들어 있을 수 있음
# BFS 구현 시에 주의 필요
graph, dead, ids, parent = dict(), [], dict(), dict()
idx = 1
for _ in range(n):
temp = sys.stdin.readline().rstrip()
if temp == "F":
graph[idx] = []
parent[idx] = idx
ids[idx] = -idx
idx += 1
m = int(sys.stdin.readline())
for _ in range(m):
temp = list(sys.stdin.readline().split())
if len(temp) == 1:
dead.append(-int(temp[0]))
else:
m = int(temp[1])
if temp[2] == "F":
graph[idx] = []
graph[m].append(idx)
parent[idx] = m
ids[idx] = -idx
idx += 1
k = int(sys.stdin.readline())
for _ in range(k):
# female인지 확인 -> graph 딕셔너리에 id 존재하는지
dna_id, dna_num = map(int, sys.stdin.readline().split())
ids[dna_id] = dna_num
if dna_id in graph:
bfs(dna_id)
find(dna_id, dna_num)
for key in graph.keys():
if parent[key] == key:
bfs(key)
for item in dead:
del ids[item]
f_temp, m_temp = set(), set()
for key in ids.keys():
if key in graph:
f_temp.add(ids[key])
else:
m_temp.add(ids[key])
cnt = 0
for item in f_temp:
if item > 0:
cnt += 1
if cnt > 1 and len(f_temp) > 1:
print("NO")
exit(0)
cnt = 0
for item in m_temp:
if item > 0:
cnt += 1
if cnt >= 2:
print("NO")
exit(0)
ans = f_temp.union(m_temp)
print("YES" if len(ans) == 1 else "POSSIBLY")
