[Python | SWEA] 2814. 최장 경로

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=2 

SW Expert Academy

 

문제

N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서의 최장 경로의 길이를 계산하자.

정점의 번호는 1번부터 N번까지 순서대로 부여되어 있다.

경로에는 같은 정점의 번호가 2번 이상 등장할 수 없으며, 경로 상의 인접한 점들 사이에는 반드시 두 정점을 연결하는 간선이 존재해야 한다.

경로의 길이는 경로 상에 등장하는 정점의 개수를 나타낸다.

 

제출 답안

 

개선 답안

dfs로 풀 수 있음

def dfs(c, v):
    global ans
    ans = max(ans, len(v))  # 정답 처리: 최대값 갱신

    for  n in adjL[c]:
        if n not in v:
            dfs(n, v+[n])

T = int(input())
for test_case in range(1, T+1):
    # N: 정점 개수, M: 간선 개수
    N, M = list(map(int, input().split()))

    adjL = [[] for _ in range(N+1)]
    for _ in range(M):
        s, e = map(int, input().split())
        adjL[s].append(e)
        adjL[e].append(s)
    
    ans = 0
    for s in range(1, N+1):
        dfs(s, [s])
    print(f"#{test_case} {ans}")

 

참고 자료

https://www.youtube.com/watch?v=Hj39HZhcnP4