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

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

2644번: 촌수계산

---

---

Solution

 

문제유형 : BFS/DFS 

 

BFS로 풀다보니까 큐에 값을 하나씩 담고 먼저 들어온 값부터 처리하느라 a와 b의 촌수가 나왔음에도 불구하고

큐에 값이 남아있으면 그걸 처리하면서 촌수(ans)가 늘어나 고생했다.

찾아본 결과 이건 큐에서 값을 빼는 횟수를 기존에 있던 큐의 개수만큼 해주면 된다.

---

 

입력으로 주어지는 관계를 arr 배열로 저장한다.

for _ in range(m):
    x, y = map(int, input().split(' '))
    arr[x].append(y)
    arr[y].append(x)

 

arr배열

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

 

촌수를 알고자 하는 a부터 bfs를 돌린다. 

a가 7이므로 visited[7]에 해당되는 값을 TRUE로 바꾸고, 7을 큐에 넣는다.

queue = [7]    ans = 0

 

촌수를 1 올리고, 큐의 개수 = 1 만큼 큐에서 값을 뺄 것 이다.

그러면 k = 7이 되고, 큐에는 arr[7]에 있는 2가 담긴다.(visited[2]의 값은 FALSE 에서 TRUE)

k = 7    queue = [2]    ans = 1

 

촌수를 1 올리고, 큐의 개수 = 1 만큼 큐에서 값을 빼자.

k = 2가 되고, 큐에는 arr[2]에 있던 visited값이 FALSE였던 1,8,9가 담긴다.

k = 2    queue = [1,8,9]    ans = 2

 

촌수를 1 올리고, 큐의 개수 = 3 만큼 큐에서 값을 빼자.

1. k = 1이 되고, 큐에는 arr[1]에 있던 visited값이 FALSE인 3이 담긴다.

2. k = 8이 되고, 큐에는 arr[8]에 있는 값 2의 visited가 TRUE이기 때문에 큐에는 아무것도 담지 않는다.

3. k = 9가 되고, 큐에는 arr[9]에 있는 값 2의 visited가 TRUE이기 때문에 큐에는 아무것도 담지 않는다.

k = 1    queue = [8,9,3]    ans = 3
k = 8    queue = [9,3]    ans = 3
k = 9    queue = [3]    ans = 3

 

촌수를 1 올리고 큐의 개수 = 1 만큼 값을 뺄 것 이다. k = 3이 된다. 

이때 우리는 b의 값이 3이라는 것을 알고 있기 때문에 여기서 k == b에 걸리고

촌수의 값을 1 내리고 리턴한다. 

k = 3    queue = []    ans = 4
return ans - 1

 

큐에 아무런 값이 없고, 위와 같이 k가 b와 같은 적이 없다면 while문을 그대로 나오게 된다.

이때는 친척 관계가 없다는 것이기 때문에 -1을 리턴해준다.

 

^_^