[Baekjoon/🥈SilverⅡ] 2644: 촌수계산

Intro

• 가장 기본적인 BFS, DFS 문제이다.
• 필자는 해당 문제를 DFS를 사용해 풀이하였다.

Algoritm👩‍💻: DFS

#22.02.03
#2644: 촌수계산

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(num, chk):
  global lst, a, b
  for j in lst[num-1]:
    if j == b:
      print(chk+1)
      check[0] = True
      return
    elif check[j] == False:
      check[j] = True
      dfs(j, chk+1)


n = int(input())
a, b = map(int, input().split())
m = int(input())
lst = [[] for _ in range(n)]

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

check = [False for _ in range(n+1)]
check[a] = True
dfs(a, 0)

if check[0] == False:
  print(-1)

• 기준이 될 x에서 부터 y까지의 촌수를 구한다.

  • x에서 시작해 dfs를 진행한다.
  • 깊이가 증가할수록 촌수도 증가시킨다.
  • 연결된 노드에 y가 있을 경우, 촌수를 +1한 값을 출력한다.
  • 친척 관계 여부는 check[0]의 값을 통해서 판단한다.

이번 포스팅은 여기서!

끝!! ~(˘▾˘~)