[SWEA] 2814 최장 경로 Python

[ 문제 ]

 

난이도:  D3

문제 번호:  2814

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&category 

Type=CODE&problemTitle=

2814&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

---

 

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

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

경로에는 같은 정점의 번호가 2번 이상 등장할 수 없으며,

경로 상의 인접한 점들 사이에는 반드시 두 정점을 연결하는 간선이 존재해야 한다.

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

 

---

 

[ 코드 ]

def dfs(i, cnt):
    global max_v
 
    for j in range(1, N+1):
        if not visited[j] and adj[i][j]:
            visited[j] = 1
            dfs(j, cnt+1)
            visited[j] = 0
    else:
        if cnt > max_v:
            max_v = cnt
 
 
for tc in range(1, int(input())+1):
    N, M = map(int, input().split())
    adj = [[0]*(N+1) for _ in range(N+1)]
    visited = [0] * (N+1)
    max_v = 0
    for _ in range(M):
        x, y = map(int, input().split())
        adj[x][y] = 1
        adj[y][x] = 1
    for i in range(1, N+1):
        visited[i] = 1
        dfs(i, 1)
        visited[i] = 0
    print(f'#{tc} {max_v}')