[백준 / python] 2644번 촌수계산

문제

우리나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 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

 

 

예제 입력 1의 상황이다.

 

---

풀이

 일단 이 입력을 배열에 저장하기로 했다. family라는 배열에 i 번째 항은 i 사람의 1촌 관계에 있는 사람들을 저장한 리스트이다. 위 예제를 입력하게 되면 다음과 같을 것이다.

family = [[], [2,3],[1,7,8,9],[1],[5,6],[4],[4],[2],[2],[2]]

이제 나는 7과 3의 촌수를 구해야 하는데 때 bfs를 통해서 두 사람의 촌수를 구하는 법을 구현하기로 했다. ( 사실 다른 방법이 있는지는 잘 모른다... ㅎㅎ )

 

이를 위해 사람들과의 촌수 관계를 기록하는 1차원 리스트를 하나 만들었다. 이름은 checked라고 하자.

checked = [0]*(n+1)

checked [n]에 기록할 숫자는 이 사람이 n번째 사람과 몇 촌 관계인지를 기록할 것이다. 그러면 n번째 사람과 비교하는 건 알겠는데 비교되는 대상은 누구인가요? -> 이 사람은 bfs라는 함수에 인자로 들어가는 사람이 될 것이다.

 

비교할 두 사람을 p와 a라고 하자. p가 bfs라는 함수에 인자로 들어갈 것인데, checked에는 그러면 p라는 사람과 다른 사람들의 촌수가 기록될 것이다. 그러면 어떤 방법으로 이를 기록하냐???

 

family [p]를 본다. 그럼 여기 p와 1촌 관계인 사람들이 기록되어 있다. 그러면 그 사람이 예를 들어 k라고 하면 checked [k]=1 이 될 것이다. 그러고 난 후 family[k]를 보게 되면 k와 1촌 관계인 사람들이 적혀있고 이 사람들은 p와 2촌 관계에 해당한다. 근데 코드를 짜다보면 100명의 사람이 있을 수 있고 몇 촌까지 있는지 모르는데 checked[k] = 1 or checked[k] = 2 이런 식으로 직접 값을 줄 수는 없다고 생각해 checked [k]에는 어떤 수가 들어가야 할지 고민을 해보았다.

 

checked[k]에는 이 k를 불러온 사람, 즉 위 예시에서는 p를 말한다. p의 1촌 관계에 해당하는 사람이 k이므로 

checked[k] = checked[p]+1

이런 식으로 기록한다면 오류 걱정 없이 잘 기록할 수 있다.

 

아래는 이런 방식으로 풀이한 나의 코드이다.

import sys
from collections import deque

def main():
    def bfs(start):
        queue = deque()
        queue.append(start)
        while queue:
            start = queue.popleft()
            for n in family[start]:
                if checked[n] == 0:
                    checked[n] = checked[start] + 1
                    queue.append(n)
    
    n = int(sys.stdin.readline())
    target1, target2 = map(int,sys.stdin.readline().split())
    family = [[] for _ in range(n+1) ]
    checked = [0]*(n+1)

    for _ in range(int(sys.stdin.readline())):
        p, a = map(int, sys.stdin.readline().split())
        family[a].append(p)
        family[p].append(a)
    
    bfs(target1)
    print(checked[target2] if checked[target2]>0 else -1)

    
    return

if __name__=="__main__":
    main()

 

https://www.acmicpc.net/problem/2644

2644번: 촌수계산