촌수계산[백준 2644] - python

from collections import deque
import sys 
input = sys.stdin.readline

def BOJ2644() :
  global graph
  global visited
  global answer

  def bfs(start) :
    queue = deque()
    queue.append([start, 0])

    while queue :
      node, relation = queue.popleft()
      for i in range(len(graph[node])) :
        if visited[i] == False and graph[node][i] == 1 :
          visited[i] = True
          answer[i] = relation + 1
          queue.append([i, relation + 1])

  n = int(input())
  A, B = map(int, input().split())
  graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
  visited = [False for _ in range(n+1)]
  answer = [-1 for _ in range(n+1)]
  m = int(input())
  for _ in range(m) :
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

  bfs(A)
  print(answer[B])

BOJ2644()

접근 방법 :

1. 가벼운 bfs 문제다.  

2. 시작점에서 간선이 연결되어있으면 1촌이다. 순회하면서 연결되어 있으면 queue에 넣어준다.

3. 전부 업데이트 하고 최종 촌수를 출력해주면 된다. 기본 bfs 로직을 알고있으면 풀수 있는 문제이다.

 

 

 

 

 

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

2644번: 촌수계산