1. 오늘의 문제
오늘 문제는 가까운 사람들끼리의 촌수를 구하는 문제이다.
촌수를 생각하면 딱 봐도 트리탐색이다.
문제
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.
입력
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
각 사람의 부모는 최대 한 명만 주어진다.
2. 원리
촌수를 그림으로 그려보니 이 문제는 너비우선탐색(BFS)로 푸는게 맞다는 생각이 들었다.
먼저 아래와 같은 가계도가 있다고 해보자.
1의 하위에 2, 3, 7이 있고, 2의 하위에 6, 4, 5가 있다.
주어진 퀴즈에서 구하고자 하는 촌수가 숫자 6과 5의 촌수라고 하자.
그럼 왼쪽의 트리를 오른쪽으로 재배치할 수 있을 것이다.
만일 깊이우선탐색을 한다면 6->2->1->3->7->4->5 순으로 탐색하지만, 너비우선 탐색을 한다면 6->2->4->5에 도달한다.
물론 두 방법 모두 정답에 도달하는 건 똑같지만, 시간은 더 적게 걸린다.
AI에게 물어보니 최단거리를 찾는 문제는 아래와 같은 이유로 BFS가 더 유리하다고 한다.
너비우선탐색(Breadth-First Search, BFS)은 최단거리를 찾는 데 유리한 이유는 다음과 같습니다
1. 레벨 순서 탐색: BFS는 시작 노드에서 가까운 노드부터 탐색합니다. 즉, 첫 번째 레벨의 모든 노드를 탐색한 후 두 번째 레벨로 넘어가므로, 최단 경로를 보장합니다.
2. 가중치가 동일한 경우: BFS는 그래프의 모든 간선이 동일한 가중치를 가질 때 최단 경로를 찾는 데 적합합니다. 이 경우, BFS는 각 노드에 도달하는 데 필요한 간선의 수가 최소가 되도록 탐색합니다.
3. 큐 자료구조 사용: BFS는 큐를 사용하여 탐색할 노드를 관리합니다. 이 구조는 FIFO(First In, First Out) 방식으로 작동하여, 먼저 들어온 노드가 먼저 탐색되도록 보장합니다. 이로 인해 최단 경로를 찾는 데 유리합니다.
4. 사이클 처리: BFS는 방문한 노드를 기록하여 사이클이 있는 그래프에서도 무한 루프에 빠지지 않고 최단 경로를 찾을 수 있습니다.
이러한 이유들로 인해 BFS는 최단 경로 문제를 해결하는 데 매우 효과적인 알고리즘입니다. 단, 가중치가 다른 간선이 있는 경우에는 다익스트라 알고리즘이나 A* 알고리즘과 같은 다른 방법을 사용하는 것이 더 적합합니다.
3. 코드
너비우선 탐색은 que를 이용한다는 걸 알고 있으니 다음 문제는 쉬웠다.
지난번에 이용했던 deque을 이용해 que에서 리스트를 빼고 넣는 방식으로 카운트를 진행했다.
from sys import stdin
from collections import deque
put = stdin.readline
numOfPeople = int(put())
me, you = map(int, put().split())
# 가계도를 받고 방문노드를 표시할 리스트, 연결을 표시할 리스트를 만든다.
numOfLink = int(put())
visited = [ 0 for x in range(numOfPeople+1) ]
linkLst = [ [] for x in range(numOfPeople + 1) ]
for num in range(numOfLink):
i, k = map(int, put().split())
linkLst[i].append(k)
linkLst[k].append(i)
for lst in linkLst:
lst.sort()
# 덱을 만들어주고 처음 시작노드의 연결을 집어넣어준다.
route = deque()
route.append(linkLst[me])
count = 0
find = True
# 답을 찾지 못했고, route가 남아있으면 반복문을 돈다.
while find and route:
# 덱에서 가장 왼쪽의 경로를 추출한다.
nowTarget = route.popleft()
count += 1
nextRoute = []
# 경로를 하나씩 돌면서 답을 찾는다.
for now in nowTarget:
# 답을 찾았다면 count를 출력하고 find를 false로 만든다.
if now == you:
print(count)
find = False
isVisited = visited[now]
if isVisited == 0:
# 만약 방문하지 않은 곳이라면, 해당 노드를 방문 표시를 한다.
# 그리고 해당 노드를 전개해서 큐에 추가한다.
visited[now] = 1
for m in linkLst[now]:
nextRoute.append(m)
if isVisited == 1:
continue
if nextRoute:
route.append(nextRoute)
# 만일 답이 없다면 -1을 출력한다.
if find:
print(-1)
5. 느낀점
처음에는 트리탐색이 무척 어렵게 느껴졌는데, 하루에 문제를 하나씩 푸는것 만으로도 실력이 많이 늘은 것 같다.
이제 더 이상 트리탐색을 for문으로 무한루프를 돌지 않게 되었다!
이것 만으로도 장족의 발전이라 생각한다.