[백준] 2644번 촌수계산 - 파이썬

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

2644번: 촌수계산

풀이:

촌수의 개념을 잘 몰라서 계속 틀렸다. 형제지간은 2촌, 부모는 1촌, 조부모가 2촌, 부모의 형제가 3촌, 부모의 형제의 자녀가 4촌이었다. 구글에서 촌수표를 참고하면 이해하기 쉽다. 그리고 입력값이 양방향인 점을 까먹으면 안 된다. 저번에도 백준 문제들은 양방향 입력인 것을 배웠는데 또 까먹었다. 백준 예시 입력값에서는 작은 수가 왼쪽에 나오고 큰 수가 오른쪽에 나온다 (1 2, 1 3, 2 7...). 백준 예시대로 생각하면 아무 문제없지만 입력값이 반대로 (2 1, 3 1, 7 2...)으로 주어지면 답이 완전히 달라진다. 백준은 왜 이렇게 불친절한지 잘 모르겠다.

 

내 코드에서는 가장 높은 부모 노드에서 부터 시작해서 1촌과 2촌인 경우 답을 출력하고 종료하도록 만들어 주었다. 그리고 촌수를 계산할 수 없는 경우를 체크해서 -1을 출력하고 종료하도록 하였다. 아직까지 종료가 되지 않았다면 배열에서 입력받은 두 사람의 값을 찾아서 더해준 뒤 답을 출력했다.

 

코드:

from collections import deque

def bfs(a):
    count = 1
    queue = deque()
    queue.append(a)
    visited[a] = count

    while queue:
        kinshipx = False
        kinshipy = False

        index = queue.popleft()

        for i in grid[index]:
            if (index == x and i == y) or (index == y and i == x):
                print(1)
                exit()

            if i == x:
                kinshipx = True
            if i == y:
                kinshipy = True

            if kinshipx and kinshipy:
                print(2)
                exit()

            if visited[i] == 0:
                visited[i] = visited[index] + 1
                queue.append(i)


n = int(input())
grid = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)

x, y = map(int, input().split())
m = int(input())

for _ in range(m):
    a, b = map(int, input().split())
    grid[a].append(b)
    grid[b].append(a)

for i in range(1, n + 1):
    if visited[i] == 0:
        bfs(i)
        if (visited[x] != 0 and visited[y] == 0) or (visited[x] == 0 and visited[y] != 0):
            print(-1)
            exit()

print(visited[x] - 1 + visited[y] - 1)