2814. 최장 경로 (SWEA)

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

출처:

SW Expert Academy

나의 풀이

def dfs(s,length):
    global max_l
    max_l=max(max_l,length)
    if length==N:
        return
    for v in graph[s]:
        if not visited[v]:
            visited[v]=True
            dfs(v,length+1)
            visited[v]=False
T = int(input())

for test_case in range(1, T + 1):
    N,M=map(int,input().split())
    graph=[[] for _ in range(N+1)]
    max_l=0
    if N==1:
        ans=1
    else:
        for i in range(M):
            n1,n2=map(int,input().split())
            graph[n1].append(n2)
            graph[n2].append(n1)
        visited=[False]*(N+1)
        for i in range(1,N+1):
            dfs(i,0)
        ans=max_l
    print(f'#{test_case} {ans}')

• dfs로 풀었다.
• 모든 node에서 시작하여 dfs로 탐색하고, 가장 긴 length값을 답으로 유지한다.