[백준] 2644번 촌수계산 - DFS (Python3)

문제와 입출력

제한 조건과 설계

제한 조건

 

1. 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. -> 노드가 최대 100개 이므로 메모리와 시간 제한이 널널하다.

2. 탐색 시작 노드에서 특정 노드에 도달하는 데 까지 거리를 묻는 문제이다. -> DFS

---

자연어 알고리즘

1. 정보를 입력 받는다.
2. 시작 노드와 탐색 노드를 설정하여 DFS 탐색을 시도한다.
3. DFS 탐색
   • 다음 노드로 이동할 때 마다 이동 거리를 1 증가시킨다.
   • 특정 노드에 도달하면 그때 까지의 이동 거리를 출력하고 프로그램을 종료한다.
   • 노드를 재방문할 때는 이동 거리를 1 감소시킨다.
4. 3번에서 특정 노드에 도달하지 못했다면 -1을 출력하고 종료한다.

---

코드

import sys
input = sys.stdin.readline

node = int(input())
start, end = map(int, input().split())
visited = [False] * (node+1)
graph = [[] for _ in range(node+1)]

for _ in range(int(input())):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[u].sort()
    graph[v].append(u)
    graph[v].sort()

distance = 0
def dfs(graph, i, visited,end):
    visited[i] = True
    global distance

    for j in graph[i]:

        if not visited[j]:
            distance += 1

            if j == end:
                print(distance)
                exit()

            dfs(graph,j,visited,end)
    
    distance -= 1

dfs(graph,start,visited,end)
print(-1)

---

세 줄 요약

1. 노드와 노드 사이의 거리를 물어보는 문제이면 DFS가 유리할 지도...
2. 노드를 재방문 했을 경우에는 거리를 1 감소시켜야 된다.
3. 노드 첫 방문 시 방문 처리.