[SWEA] Q2814 최장경로

[SWEA] Q2814 최장경로

Question

Language: Python

Difficulty: D3

이번 문제를 살펴보면 경로 중 가장 길이가 긴(가중치의 크기가 모두 같으므로 노드의 개수를 의미) 경로의 길이를 구하는 것이다.

처음에 문제를 봤을때는 가장 큰 component의 크기를 구하면 될 것 같아서, bfs을 활용하여 component을 구하였다. 하지만 이는 틀린 풀이다.

아래의 그림을 살펴보면, component의 최대 크기와 최장 경로의 길이가 다름을 확인할 수 있다. 즉, component가 아닌, dfs을 통한 최장 path을 구하는 것이 이번의 문제의 핵심이다.

Solution

def solution(visited, vertex, length):
    global max_length

    for adj_vertex in graph[vertex]:
        if adj_vertex not in visited:
            max_length = max(max_length, length + 1)
            solution(visited + [adj_vertex], adj_vertex, length + 1)


if __name__ == "__main__":
    n,m=0,0
    graph=[]
    max_length=0
    with open("input.txt","r" ) as file:
        test_cases=int(file.readline())
        for case in range(test_cases):
            n,m=map(int,file.readline().split())
            graph=[[] for _ in range(n+1)]
            max_length=0
            for _ in range(m):
                v1,v2=map(int,file.readline().split())
                graph[v1].append(v2)
                graph[v2].append(v1)
            for i in range(1,n+1):
                solution([i],i,1)
            print(f"#{case+1} {max_length}")