[Python] SWEA 2814번 최장경로

문제

SW Expert Academy

문제 풀이

• 노드 수 만큼 dfs탐색을 진행하여, 재귀를 진행한 횟수를 세면 깊이를 알 수 있다.
• 출발 노드에서 모든 노드로 각각 탐색을 진행하고, 탐색 중 깊이가 이전 깊이보다 깊을 때 마다, max_val의 값을 갱신한다.
• 재귀를 마친 후, 다시 탐색을 진행해야 하므로 방문 리스트의 값을 다시 해제 한 후, 모든 탐색을 마쳤다면 max_val의 값을 리턴 후, 형식에 맞게 출력한다.

코드

def dfs(now, cnt):
    global max_val
    if max_val < cnt:
        max_val = cnt
    visited[now] = True
    for i in graph[now]:
        if not visited[i]:
            dfs(i,cnt+1)
    # 방문배열 해제해주기
    visited[now] = False

t = int(input())
for tc in range(t):
    n,m = map(int,input().split())
    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    for _ in range(m):
        x,y = map(int,input().split())
        graph[x].append(y)
        graph[y].append(x)

    max_val = 0
    for i in range(n + 1):
        dfs(i,1)
    print(f'#{tc + 1}',max_val)