[SWEA] 2814 | 최장경로

문제링크

---

2814 | 최장경로

풀이과정

---

DFS를 이용해서 풀어주면 된다.

이미 방문했던 노드는 재방문 하지않고, 연결되어 있는 노드 중 방문하지 않은 노드로 가게 해서 경로의 길이를 계산하자.

코드

---

def dfs(x, cnt):
    global result
    visited[x] = 1

    for i in graph[x]:
        if visited[i] == 0:
            visited[i] = 1
            dfs(i, cnt + 1)
    visited[x] = 0
    if result < cnt:
        result = cnt

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    result = 0

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

    for i in range(1, N+1):
        visited = [0] * (N+1)
        dfs(i, 1)

    print(f'#{tc} {result}')

결과

---