[백준 1003 실버2] 피보나치 함수

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

2644번: 촌수계산

해결방안

• DFS를 이용하여 해결

알고리즘

1. 결과 값을 위한 전역 변수를 초기값 -1로 초기화 (연관관계가 없을 경우를 대비)
2. 주어진 노드 값들을 딕셔너리로 생성
3. 관계들을 딕셔너리에 리스트 값으로 양방향으로 추가해줌
4. 방문여부를 확인하기 위한 리스트 초기화
5. DFS 작성
   1. 현재의 노드 값이 원하는 노드 값과 같을 경우 촌수계산을 전역 변수에 저장하고 종료
   2. 현재 노드와 관계있는 딕셔너리의 관계값(리스트)를 가지고 와서 순회
   3. 리스트에 있는 노드들을 하나씩 꺼내오면서 방문하지 않았을 경우 방문 목록에 넣고 DFS 시작
   4. DFS를 할때는 cnt변수의 값들은 1씩 추가해서 실행
6. 결과 값 출력

핵심 팁

• 전형적인 DFS를 이용한 방식
• DFS를 짜는 틀을 머릿속에 기억해두면 전형적인 방식으로 구현 가능
• 방문여부를 확인하는 로직인 visited의 pop은 수행할 필요 없음
  • 어차피 방분한 상태에서 다 순회 돌기 때문에 사실상 불필요한 로직

import sys
result = -1

def main():
    input = sys.stdin.readline
    n = int(input())
    src, des = map(int, input().strip().split())
    cousins = dict()
    for i in range(1, n + 1):
        cousins[i] = []

    relations = int(input())
    for _ in range(relations):
        a, b = map(int, input().strip().split())
        cousins[a].append(b)
        cousins[b].append(a)

    visited = []
    dfs_cousin(src, des, cousins, visited, 0)

    print(result)

def dfs_cousin(a, b, rel, visited, cnt):
    global result
    if a == b:
        result = cnt
        return
    for node in rel[a]:
        if node not in visited:
            visited.append(node)
            dfs_cousin(node, b, rel, visited, cnt + 1)
            # 어차피 dfs로 계속 파고 들어가니까 굳이 pop안해줘도 됨
            visited.pop()

main()