SW Expert Academy

D3 2814번 최장경로(python)

문제

풀이과정

재귀함수를 이용한 DFS
각각의 노드에서 DFS 수행, 사이클이 없는 경로가 이어지는 경우 경로의 길이(노드의 개수)를 카운트
경로 탐색시 파생되는 경로를 모두 탐색하기 위해 방문한 노드의 방문 여부를 False로 지정

소스코드

T = int(input())

for t in range(T):
    vertex, edge = map(int, input().split())
    graph = [[] for _ in range(vertex + 1)]

    for i in range(edge):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    result = 0

    for i in range(1, vertex + 1):
        visited = [False] * (vertex + 1)

        def dfs(v, count):
            global result
            visited[v] = True
            result = max(result, count)
            for x in graph[v]:
                if not visited[x]:
                    dfs(x, count+1)
                    visited[x] = False

        dfs(i, 1)

    print("#{} {}".format((t+1), result))