문제
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.
입력
- 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다.
- 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다.
- 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다.
- 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다.
이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. - 각 사람의 부모는 최대 한 명만 주어진다.
출력
- 입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다.
- 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다.
- 이때에는 -1을 출력해야 한다.
예제
입력 1
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6출력 1
3입력 2
9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6출력 2
-1풀이
클래스를 만들어서 풀었다. 이 문제에서 헤맸던 것은 파이썬에서 클래스를 오랜만에 만들어서 잠깐 헷갈린거랑 cnt를 전역변수로 만들었더니 촌수가 세지는 것이 아니라 계산한 전체 수가 세지는 것이었다. 어렵지 않게 해결했지만 더 좋은 방법은 존재할 것 같다.
from collections import deque
# Person 클래스 정의
class Person:
# 생성자
# num이 본인 번호, parent와 child가 입력되지 않으면 None으로 지정
def __init__(self, num, parent=None, child=None):
self.num = num
self.parent = parent
self.children = [child] # 자식은 여러명이 가능하므로 리스트로 만듦
def setParent(self, parent):
self.parent = parent
def addChild(self, child): # 자식 추가할 때
self.children.append(child)
if None in self.children: # 리스트에 None이 있으면 삭제
self.children.remove(None)
def getParent(self):
return self.parent
def getChildren(self):
return self.children
n = int(input())
p1, p2 = map(int, input().split()) # 찾을 촌수
m = int(input())
person = {} # 사람들 번호 당 Person 객체 저장할 딕셔너리
for _ in range(m):
parent, child = map(int, input().split())
# 부모가 person에 저장된 적 없으면
if parent not in person:
# Person 객체 생성 후 딕셔너리에 저장
p_parent = Person(parent, child=child)
person[parent] = p_parent
# person에 저장되어있으면 자식 추가
else:
person[parent].addChild(child)
# 자식 또한 부모와 마찬가지로 실행
if child not in person:
p_child = Person(child, parent=parent)
person[child] = p_child
else:
person[child].setParent(parent)
queue = deque([[p1, 0]]) # bfs에 사용할 큐. 두번째 원소는 p1과의 촌수
check = set() # 촌수 여부 확인한 사람
isFound = False # p2와의 촌수 확인 여부
# bfs 시작
while queue:
p, cnt = queue.popleft() # 사람, 촌수
if p == p2: # 이번 사람이 p2이면 촌수 계산, 출력
isFound = True
print(cnt)
break
check.add(p) # 이번 사람 체크.
n_person = person[p] # Person 객체 가져옴
parent = n_person.getParent() # 부모
child = n_person.getChildren() # 자식
# 부모를 존재하고 아직 체크 안했으면 큐에 추가
if parent not in check and parent is not None:
queue.append([parent, cnt + 1])
child = list(set(child) - check) # 자식 중 체크한 자식은 제거
# 자식 리스트를 2차 리스트로 변환. [자식 번호, 촌수] 형태의 리스트
child = list(zip(child, [cnt+1 for _ in range(len(child))]))
# 자식 리스트 중 자식 번호가 None이 하나도 없으면 큐에 자식 리스트 추가
if all(None not in c for c in child):
queue += child
# 촌수 계산 실패 시, -1 출력
if not isFound:
print(-1)
컴퓨터 관련 여러 분야 공부중