[BOJ 2644] 촌수계산

Depth First Search

[BOJ 2644] 촌수계산

문제

구조화

• Node의(사람) 개수 n 정의
• 검색 대상이 되는 노드 target1, target2 정의
• Edge의(몇 촌) 개수 m 정의
• Node와 edge를 기준으로 그래프 생성
• 주의할 점은, 무방향 그래프이기에 양쪽 Edge를 모두 추가하는 형식으로 Graph 구현
• 방문 처리를 위한 State 생성
• 방문하는 순서인 cnt 정의
• 재귀 호출을 실행하며 cnt를 State에 저장
  • 이를 통해, target1의 방문순서와 target2의 방문순서의 차이는 몇 촌 관계인지를 나타낼 수 있음
  • 만약, target1이나, target2 중 하나 이상 cnt가 0인 경우 서로 이어질 수 없는 관계이므로 -1을 Return
• 입력된 target 중 더 큰 수를 기준으로 DFS 시작

예제 시각화

해답

import sys
sys.setrecursionlimit(150000)
input = sys.stdin.readline

n=int(input()) # 노드 개수

target1, target2 = map(int,input().split()) # 검색 대상
cnt=1 # 방문 순서 정의, cnt를 가산하며 촌수 계산
m=int(input()) # Edge, 즉 노드 간 관계의 수

graph = [[] for i in range(n+1)] 

state = [0 for _ in range(n+1)]

for i in range(m): # 무방향 그래프
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def recur(node):
    global cnt # global을 통해 함수 내부에서도 활용
    state[node]=cnt # 방문 순서를 state에 저장
    
    for nxt in graph[node]: 
        if state[nxt]==0: # 방문하지 않았다면?
            cnt+=1 # 촌 수 가산
            recur(nxt) # 다음 촌 수 호출
    cnt = cnt-1 # 시작 정점을 1로 설정했기에, -1을 하여 촌수 계산

recur(max(target1,target2)) # 탐색 시작
if state[target1]!= 0 and state[target2]!=0: # 만약 target 중 하나 이상이 0이라면 방문할 수 없는 노드
    print(abs(state[target1]-state[target2])) # 둘 다 0이 아니면 촌 수 출력
else:
    print(-1) # 하나 이상 0이면 -1 출력