[BOJ / 백준] 2644 촌수계산 (S2 / DFS) - Python

링크

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

 

 

 

 

문제 해석

촌수계산
부모-자식 관계는 1촌
더 멀어지는 경우 촌수가 늘어남


입력
첫 번째 줄 : n
  n : 사람 수
두 번째 줄 : a, b
  촌수를 구해야 하는 사람
세 번째 줄 : m
  m : 부모 자식 관계 수
나머지 줄 : m개의 부모 자식 관계

 

출력
두 사람의 촌수를 출력
촌수를 나타낼 수 없으면 -1

 

 

 

 

풀이 & 코드 해석

어제 풀었던 바이러스와 다르게 촌수계산은 a라는 노드와 b라는 노드가 얼마나 떨어져 있는지를 계산해야 합니다.

 

따라서 그래프를 순회하면서 시작 정점으로부터 얼만큼 떨어져 있는지를 매개변수로 추가하여 문제를 해결하였습니다.

 

 

 

 

코드

def dfs(num, dis):
    global b, ans
    v[num] = True

    for nxt in graph[num]:
        if v[nxt] == True:
            continue

        if nxt == b:
            ans = dis
            return

        dfs(nxt, dis + 1)


n = int(input())

a, b = list(map(int, input().split()))

m = int(input())

graph = [[] for _ in range(n + 1)]
v = [False] * (n + 1)

for _ in range(m):
    c, d = list(map(int, input().split()))
    graph[c].append(d)
    graph[d].append(c)

ans = -1
dfs(a, 1)
print(ans)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java