[백준 2644번] 촌 수 계산

from collections import deque

# 전체 사람 수(n)
n = int(input())

# 촌수를 계산해야 하는 두 사람
target_a, target_b = map(int,input().split())

# 부모 자식들 간의 관계의 개수
m = int(input())

# 전체 사람의 부자 관계를 나타내는 2차원 리스트
graph = [[] for _ in range(n+1)]

# 확인 여부 확인용 리스트
visited = [False] * (n+1)

# 친척 관계를 저장하는 리스트
relation = [0]*(n+1)
relation[target_a] = 0

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

def bfs(graph,v,visited):

  visited[v] = True

  queue = deque([v])

  while queue:

    popped =  queue.popleft()

    for i in graph[popped]:
      if not visited[i]:
        visited[i] = True
        queue.append(i)
        relation[i] = relation[popped]+1

bfs(graph,target_a,visited)

if relation[target_b] == 0:
  print(-1)
else:
  print(relation[target_b])

이번 문제는 여러가지 부모관계가 주어진 상황에서, 특정한 사람(정점)에서 다른 사람(정점)까지 몇 촌 관계(거리)에 있는지 확인하는 문제로, 굉장히 흥미로운 주제의 문제였다.

 

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

먼저 부모관계는 두 정점이 서로 가지고 있는 양방향 관계이기 때문에 양방향 그래프의 형식으로 저장해주었다.

 

def bfs(graph,v,visited):

  visited[v] = True

  queue = deque([v])

  while queue:

    popped =  queue.popleft()

    for i in graph[popped]:
      if not visited[i]:
        visited[i] = True
        queue.append(i)
        relation[i] = relation[popped]+1

또한 특정 정점에서 다른 정점까지의 거리를 기록해야 하기 때문에 BFS 알고리즘을 사용하였다 !

 

마지막으로 특정 사람을 기준으로 다른 사람들의 친척 관계를 저장하기 위한 배열(relation)을 사용함으로써 최종적인 답을 얻을 수 있었다.

 

BFS 알고리즘을 양방향 그래프의 방식으로 풀어볼 수 있었던 흥미로운 문제였다 :)