[boj] 촌수계산_2644

www.acmicpc.net/problem/2644

2644번: 촌수계산

어떻게 풀지 어떻게 풀지 이게 왜 실버문젤까 하면서 꽤 오래 고민했던 문제다.

 

BFS문제는 격자 혹은 좌표형태의 문제만 풀어봐서 그런지 어떻게 BFS로 푼다는 말인가 오랫동안 이해가 안갔었지만 큐를 이용해 갈 좌표들을 하나 씩 점검해주는 방식으로 푸니 이게 결국 BFS였다.

 

문제의 TC로 나온 예를 이용해 설명해보면, 처음에는 위와 같은 형태의 계층 구조가 있고 빈 큐를 이용한다.

 

우리는 3과 7의 촌수를 계산해야 하는데 어떻게 하면 좋을까?

내가 이용한 방법은 아래와 같다.

1. 모두의 촌수를 0으로 둔다.

2. 촌수를 계산하려는 두 사람 번호 중 하나의 번호에서 탐색을 시작한다.

3. 현재 방문한 사람을 큐에서 빼고 부모/자식 구분 없이 연결된 모든 사람 중 방문하지 않은 사람을 큐에 집어넣고 방문체크를 한다.

4. 만약 큐에서 뺀 사람이 방문한 사람이라면 넘어가고, 방문하지 않았던 사람이라면 방문 체크하고 촌수를 1씩 더해준다.

5. 2번과 3번을 반복하다가 촌수를 계산하기로 한 상대방이 등장하면 촌수를 따지고 종료한다.

6. 만약 두 사람이 촌수 관계가 없다면(ex. 3번과 4번) 큐가 빌 때 까지 둘 중 하나의 촌수가 0일 것이다. 

이게 무슨말이야? 위 설명을 그림을 그려 설명해보자면 아래와 같다.

필자는 아래와 같은 연결 상태를 표현하기 위해 인접리스트를 이용했다.

 

우리는 3번 혹은 7번에서 탐색을 시작한다.

둘 중 어느 번호로 시작해도 상관없다. 관례상 사용하는 작은 숫자로부터 시작해도 되고 이해하기 쉽게 끝에서부터 밀고 올라가도 된다.

필자는 3번부터 시작하겠다.

 

처음에는 시작하는 번호인 3번이 큐에 들어가 있다. 그리고 모두의 (3번으로부터의) 촌수는 0이다.

 

큐에서 맨 앞 번호를 빼고 연결된 모든 번호를 큐에 집어넣는다. 이 경우, 3번에 연결된 번호는 1번이므로 1번을 큐에 집어넣는다.

그리고 1번의 촌수를 3번의 촌수인 0에 1을 더해 1로 바꾼다.

 

1번을 큐에서 빼고 방문처리한 후 연결된 번호인 2번을 큐에 넣는다. 그리고 2번의 촌수를 1번의 1에서 1을 더한 2로 바꾸어 준다.

 

2번을 큐에서 빼고 연결된 번호인 7번, 8번, 9번을 큐에 넣는다. 2번은 기존에 방문했던 번호로 방문처리가 되어있으므로 넣지 않는다.

7번 8번 9번의 촌수를 2의 촌수인 2에서 1을 더한 3으로 바꾸어 준다. 1번은 이미 방문했던 번호이므로 촌수를 바꾸어 주지 않는다.

 

같은 원리로 7번, 8번, 9번을 모두 꺼낸다. 7, 8, 9번에 연결된 번호인 2번은 이전에 이미 방문처리되었으므로 촌수가 변하지 않고 큐에 들어가지도 않는다.

 

만일 촌수 관계가 없는 두 번호가 선택되었다면 위 그림처럼 연결되지 않기 때문에 촌수가 그대로 0일 것이다.

 

# 촌수계산 https://www.acmicpc.net/problem/2644
from collections import deque

queue = deque()

n = int(input())
# 찾을 사람 2명 입력
p1, p2 = map(int, input().split())
m = int(input())

visited = [False] * (n+1)

array = [[] for _ in range(n+1)]
count = [0] * (n+1)

for _ in range(m):
    # 부모 자식 관계 입력
    p, d = map(int, input().split())
    array[p].append(d)
    array[d].append(p)

queue.append(p1)

while queue:
    temp = queue.popleft()
    visited[temp] = True

    for i in array[temp]:
        if not visited[i]:
            queue.append(i)

    for i in array[temp]:
        in not visited[i]:
            count[i] = count[temp]+1
        else:
            continue

if count[p2] != 0:
    print(count[p2])
else:
    print(-1)