[Python] 18126번 너구리 구구

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

18126번: 너구리 구구

---

 

22/09/19

 

 

그룹원들과 푼 그룹 주간 문제로 이 문제를 선택해서 풀었다.

 

오랜만에 DFS문제, 그것도 일반적인 matrix모양으로 간선이 주어지는 것이 아닌 실제 간선 모양으로 주어지는 그래프라서 조금 헷갈리긴 했지만 더듬더듬 기억을 되살려 가며 주석을 달아가며 작성했던 문제이다.

---

 

문제 접근 방식:

 

 

처음에는 이 문제를 재귀 오류로 틀렸었다. (재귀 제한 코드를 실수로 적지 못했다.)

 

어찌 되었건 간에, 이 문제는 언뜻 보아서 길의 길이가 최대가 되도록 해야 하므로 다익스트라 알고리즘이라고 생각할 수 있다.

 

실제로 나도 언뜻 문제를 봐서 선정을 했기 때문에 이 문제가 왜 DFS문제인지를 이해를 못 했기도 했다.

 

이 문제의 핵심은 이 그래프가 사이클이 없다는 점이였다.

 

방은 총 N개인데, 간선은 N-1개이고, 방들끼리는 모두 오고 갈 수 있다는 말이 언급이 되어 있으므로 만약 그래프에 사이클이 존재한다면 간선의 개수가 더 많아야 하기 때문에 모순이 생길 수밖에 없기 때문이다.

 

때문에 이 그래프는 사이클이 존재하지 않으므로 트리 구조를 띄고 있다.

 

그래서 단순한 DFS로도 풀릴 수 있는 것이었다.

 

DFS를 진행하면서 말단 노드까지 계속 길을 갔다가, 돌아오는 방식을 취해주었다.

 

탐색을 진행할 때에는 지금까지 갔던 거리 + 앞으로 갈 간선의 거리를 함수 인자로 받아 출발점으로부터의 거리가 얼마큼 되는가를 나타내 주었다.

 

말단 노드에 도착을 하면, 거리가 지금까지 나왔던 거리 중에 최대 거리인지 확인하고, 맞다면 갱신을 해주는 방식으로 진행하였다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 18126번 너구리 구구
# 그래프 이론, 그래프 탐색, 트리, DFS, BFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    node1, node2, road_distance = map(int, input().rstrip().split())
    graph[node1].append((node2, road_distance))
    graph[node2].append((node1, road_distance))
visited = [0 for _ in range(N+1)]
max_distance = 0

def DFS(now_node, total_distance):  # 현재 노드와 지금까지 간 거리
    global max_distance
    if len(graph[now_node]) == 1 and not now_node == 1:  # 말단 노드면
        if total_distance > max_distance: # 최대 거리면 갱신
            max_distance = total_distance
        return
    # 말단 노드가 아니면 계속 탐색
    for node, distance in graph[now_node]:
        if visited[node] == 0:
            visited[node] = 1
            DFS(node, total_distance + distance)
            visited[node] = 0

visited[1] = 1
DFS(1, 0)
print(max_distance)