[BOJ] 1167 : 트리의 지름 [그래프이론/트리](Python)

문제 링크

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

1167번: 트리의 지름

소스 코드

import sys
sys.setrecursionlimit(10**6)

def main():
    v = int(input())
    graph = [[] for _ in range(v+1)]
    visited = [False] * (v+1)
    distances = [0] * (v+1)

    for _ in range(v): # 그래프 입력 받기
        temp = list(map(int,sys.stdin.readline().strip().split()))
        start = temp[0]
        for i in range(1, len(temp)-1, 2):
            graph[start].append((temp[i], temp[i+1]))

    dfs(1, graph, visited, distances) # 임의의 시작 노드에서 가장 먼 노드

    u = max(range(1,v+1), key=lambda x: distances[x]) # 거리가 가장 먼 노드

    visited = [False] * (v+1) # 초기화
    distances = [0] * (v+1)

    dfs(u, graph, visited, distances) # 가장 먼 노드에서 다시 탐색

    v = max(range(1,v+1), key=lambda x: distances[x]) # 가장 먼 노드

    print(distances[v])

def dfs(node, graph, visited, distances):
    visited[node] = True
    for neighbor, weight in graph[node]:
        if not visited[neighbor]:
            distances[neighbor] = distances[node] + weight
            dfs(neighbor, graph, visited, distances)

if __name__ == '__main__':
    main()

 

해설

• 그래프, 트리, DFS

다른 풀이를 참고해보니 BFS로도 충분히 가능하더라구요.
역시 BFS/DFS는 거의 호환되는 것 같습니다.

(상황에 따라 좀 더 편리한 것을 취사선택하면 될 것 같아요)

 

시간복잡도

이 알고리즘의 시간복잡도는 O(V) 입니다.

DFS를 통해 노드를 탐색하게 되면 '모든 노드'를 방문하게 됩니다.
따라서 노드의 개수인 V만큼 탐색을 수행하는 것입니다.

탐색 과정에서 '이동 가능한 노드'를 추가 탐색하거나 거리를 계산하는 등의 작업도 '상수배'이고,

DFS 자체도 두 번 적용하기 때문에 '상수배'이므로 총 시간복잡도는 O(V)로 계산됩니다.

그래프 입력/초기화

for문의 범위를 잘 설정해야 합니다.

첫 번째 숫자는 출발 노드이고 나머지 숫자는 (도착 노드, 가중치) 로 묶여야 하기 때문에 range의 step을 2로 두면 됩니다.

 

또한 방문 여부를 확인할 리스트와 가중치를 합하여 거리를 기록할 리스트를 초기화 해줍니다.

 

첫 번째 DFS

이 포스팅에서는 이런 알고리즘을 적용하는 이유에 대해서는 다루지 않을 예정입니다.

전제가 모순됨을 통해 증명하는 여러 방식들이 있는데 필요하다면 검색해보시길 권장드립니다.

 

과정은 이렇습니다.

'임의의(정말 아무 노드여도 상관 없습니다)' 정점으로부터 가장 먼 정점을 DFS로 찾는다.

이 가장먼 정점으로부터 가장 먼 정점을 찾아 정답으로 반환한다.

def dfs(node, graph, visited, distances):
    visited[node] = True
    for neighbor, weight in graph[node]:
        if not visited[neighbor]:
            distances[neighbor] = distances[node] + weight
            dfs(neighbor, graph, visited, distances)

우리는 그래프에 한 정점으로부터 이동 가능한 정점과 가중치를 저장해두었습니다.

따라서 방문한 적이 없는 정점이라면 방문처리를 하면서 가중치를 더하여 거리 리스트에 기록하도록 합니다.

한 번 DFS를 돌리고 나면 임의의 정점으로부터 가장 먼(가중치가 컸던) 정점을 구할 수 있게 됩니다.

 

두 번째 DFS

이번에는 이 정점을 기준으로 다시 DFS를 수행합니다.

그렇게 되면 이 그래프 내에서 가장 거리가 긴 두 개의 노드 간 거리를 구할 수 있게 됩니다.

 

거리가 가장 멀었던 노드를 찾는 가벼운 테크닉

거리를 저장하는 리스트에 단순히 max 함수를 적용하면 '노드'가 아니라 '거리'가 나오게 됩니다.

우리는 추가 탐색을 수행해야 하므로 range와 lambda를 이용하여 '노드'를 구할 수 있습니다.

u = max(range(1,v+1), key=lambda x: distances[x]) # 거리가 가장 먼 노드
v = max(range(1,v+1), key=lambda x: distances[x]) # 가장 먼 노드

이때 범위가 1부터 v(정점의 개수)까지가 될 수 있도록 세팅해줘야 합니다.