백준 2644번 바로가기

나의 풀이

n = int(input())
a,b = map(int,input().split())
m = int(input())
vertexList = [[] for _ in range(n+1)]
visitedList = [False] * (n+1)
result = []

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


def dfs(vertex, num):
  num += 1
  visitedList[vertex] = True

  if vertex == b:
    result.append(num)

  for vertex in vertexList[vertex]:
    if not visitedList[vertex]:
      dfs(vertex, num)

dfs(a,0)
if not result:
  print(-1)
else:
  print(result[0]-1)

CODE REVIEW

  1. 그래프 이론을 이용하여 촌수를 구하는 문제. DFS 함수 구현 과정에서 예상한 결과와 실행값이 달라서 고민을 많이 했다.
  2. vertexList와 visitedList를 만들 때에 range(n+1)로 잡으면 index번호와 vertex번호가 같아져서 편리해진다.