[SWEA] 2814. 최장 경로(python)

📌문제

💪아이디어

1. 그래프 간선표시
   2차원배열로 표시할 수 도 있지만 defaultdict이 더 편해서 딕셔너리를 사용하였다. key는 노드번호, value는 연결된 노드의 번호
2. 노드 방문
   dfs를 사용하였다. 해당 노드와 연결된 간선이 있는 노드를 돌면서 visited를 사용하여 해당 노드를 방문했는지 체크했다.

   🥂코드

from collections import defaultdict

def dfs(node, visited, cnt):
    global answer
    if answer < cnt: answer = cnt
    for nxt_node in graph[node]:
        if not visited[nxt_node]:
            visited[nxt_node] = True
            dfs(nxt_node, visited, cnt + 1)
            visited[nxt_node] = False

T = int(input())
for tc in range(1, T + 1):
    n, m = map(int, input().split())
    graph = defaultdict(list)
    answer = 0
    if m==0: answer=1
    else:
        for _ in range(m):
            x, y = map(int, input().split())
            graph[x].append(y)
            graph[y].append(x)

        visited = [False] * (n + 1)
        visited[0] = True
        for node in range(1, n + 1):
            visited[node] = True
            dfs(node, visited, 1)
            visited[node] = False
    print('#{} {}'.format(tc, answer))