[백준 알고리즘] 1167번 Python 풀이

그래프 - 1260, 11724, 1707, 10451, 2331, 9466, 2667, 4963, 7576, 2178, 2146, 1991, 11725, 1167, 1967

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

알고리즘 문제풀이(PS) 시작하기

 

 

 

1167번과 이 다음 1967번은 구조가 유사하다. 입력값을 부분을 제외하면 동일한 구조로 정답을 받을 수 있다. 1167번을 다른 분의 풀이를 보고 풀었고, 1967번은 이를 다시 입력 부분만 바꿔 제출했는데 정답 결과는 받았지만 약간의 오류아닌 오류?(답을 구하는 데는 문제가 없기 때문)를 찾게 되었다.

 풀이 참조:  developmentdiary.tistory.com/436

import sys
v = int(sys.stdin.readline())
node_graph = [[] for _ in range(v+1)]
for i in range(v):
    path = list(map(int, sys.stdin.readline().split()))

    # 각 입력 Line의 정보를 받아 Parsing 후 node_graph에 연결 정보 저장
    path_len = len(path)
    for i in range(1, path_len//2):
        node_graph[path[0]].append([path[2*i-1], path[2*i]])


# 첫 번째 DFS 결과
result_first = [0 for _ in range(v+1)]


def DFS(start, matrix, result):
    for e, d in matrix[start]:
        if result[e] == 0:
            result[e] = result[start]+d
            DFS(e, matrix, result)


DFS(1, node_graph, result_first) # 아무 노드에서 시작해준다
result_first[1] = 0 # 루트 노드가 정해져 있지 않아 양방향으로 입력을 받기 때문에 해당


tmpmax = 0 # 최댓값 구하기
index = 0 # 최장경로 노드

for i in range(len(result_first)):
    if tmpmax < result_first[i]:
        tmpmax = result_first[i]
        index = i

# 최장경로 노드에서 다시 DFS를 통해 트리의 지름을 구함
result_final = [0 for _ in range(v+1)]
DFS(index, node_graph, result_final)
result_final[index] = 0
print(max(result_final))

 

트리의 지름은 1) 임의의 한 노드 x에서 가장 먼 노드 y를 찾고, 2) 그 y 노드에서 가장 거리가 먼 노드 z를 찾아 3) y와 z 노드 사이의 길이를 찾아주면 된다. 이에 대한 증명은 아래 블로그에 잘 설명되어 있다. 
https://blog.myungwoo.kr/112

위 구현 코드는 사실상 풀이를 참조했던 블로거분의 코드와 변수명 정도만 다를뿐.. 같은 코드다.
그런데 DFS를 정의하는 부분에서 이와 같이 구현할 때, 트리의 지름을 구하는 데 문제는 없지만 DFS를 한 번 돌고 나왔을 때 결과가 DFS를 시작하는 부분으로부터의 거리임을 고려할 때 정확히 계산되지 않는 상황이 발생할 수 있다.

이러한 상황은 1967번의 예제처럼 이진트리와 유사하게 양쪽으로 찢어진 모양에서 발생할 수 있는데, DFS를 시작하는 임의의 노드 x가 탐색을 시작할 때 한 쪽 방향을 모두 탐색하고, 반대쪽 방향을 탐색하는 시점에서 x까지의 거리가 항상 0임을 구현과정에서 만족시켜주지 못하기 때문이다.(DFS 계산 당시가 아니라, 계산 후 result_first[1] = 0 으로 값을 바꿔줌)

 

1167번 예제 그래프와 1967번 예제 그래프

결과적으로 1967번 그래프에서는 첫 번째 DFS를 돌고 나서 우측에 위치한 노드까지의 길이가 모두 6만큼 증가해 계산된다.
그러나 결과적으로 트리의 지름을 구하는데는 문제가 없는데, 그 이유는 다음과 같다.

노드1에서 DFS를 한 번 수행했을 때, 가장 먼 거리를 갖고 있는 노드는 반드시 1) 좌측에 존재하거나, 2) 우측에 존재한다.
1)좌측에 존재하는 경우 해당 노드에서 가장 먼 거리를 갖는 노드는 반드시 노드 1의 우측에 존재한다. 또, 2)우측에 존재하는 경우 해당 노드에서 가장 먼 거리를 갖는 노드는 반드시 노드 1의 좌측에 존재한다. 쉽게 말하면, DFS로 한 쪽 방향으로 가장 먼 거리의 노드를 구하게 되는데, 이 때 위와 같이 6이라는 잘못된 값이 더해져 위 그래프에서 원래는 좌측에 가장 먼 거리의 노드가 위치하더라도 첫 DFS 결과 가장 먼 거리의 노드를 우측에 있는 것으로 판단하는 상황이 있을 수 있다. 그러나 반드시 한 쪽 방향 내에서 가장 먼 거리의 노드이기 때문에, 다시 한 번 DFS를 거쳐 트리의 지름을 구하는데는 문제가 없는 것이다.

만약 그래도, 첫 DFS 결과또한 깔끔하게 구하고 싶다면 아래와 같이 DFS 정의할 때, 변수를 하나 더 생성해 한 번 지나간 노드는 값을 바꾸지 않도록 하면 된다.

import sys
v = int(sys.stdin.readline())
node_graph = [[] for _ in range(v+1)]
for i in range(v):
    path = list(map(int, sys.stdin.readline().split()))

    # 각 입력 Line의 정보를 받아 Parsing 후 node_graph에 연결 정보 저장
    path_len = len(path)
    for i in range(1, path_len//2):
        node_graph[path[0]].append([path[2*i-1], path[2*i]])


# 첫 번째 DFS 결과
result_first = [0 for _ in range(v+1)]


def DFS(start_node, now_node, matrix, result):
    for e, d in matrix[now_node]:
        # 경로 정보가 입력되지 않은 간선
        # *** result[start]는 항상 0이어야 하므로, 값을 변경하면 안된다 *** 주의!
        if result[e] == 0 and e != start_node:
            result[e] = result[now_node]+d
            DFS(now_node, e, matrix, result)


DFS(1, 1, node_graph, result_first) # 아무 노드에서 시작해준다
result_first[1] = 0 # 루트 노드가 정해져 있지 않아 양방향으로 입력을 받기 때문에 해당

tmpmax = 0 # 최댓값 구하기
index = 0 # 최장경로 노드

for i in range(len(result_first)):
    if tmpmax < result_first[i]:
        tmpmax = result_first[i]
        index = i

# 최장경로 노드에서 다시 DFS를 통해 트리의 지름을 구함
result_final = [0 for _ in range(v+1)]
DFS(index, index, node_graph, result_final)
result_final[index] = 0
print(max(result_final))