[BOJ] 백준 2644 촌수계산

태환·2024년 3월 2일
0

Coding Test

목록 보기
100/151

📌 [BOJ] 백준 2644 촌수계산

📖 문제

📖 예제

📖 풀이

import sys
input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(int(input())):
  x, y = map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)

ans = 0
visited = [0] * (n+1)
def DFS(x, cnt):
  if x == b:
    global ans
    ans = cnt
  for i in graph[x]:
    if visited[i] == 0:
      visited[i] =  1
      DFS(i, cnt + 1)

DFS(a, 0)
if visited[b] == 0:
  print(-1)
else:
  print(ans)

DFS를 이용하여 문제를 해결한다.
DFS 수행 중 목표 지점에 대해 DFS가 수행되었을 경우 cnt 값을 저장해놓고 결과로 출력한다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글