[SWEA] 2814_최장 경로

📕 문제

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

SW Expert Academy

 

💡 풀이법

1. 시작점이 정해져있지 않기 때문에 모든 노드를 시작점으로 하고 dfs를 돌려봐야 한다.

2. dfs 재귀를 구현했는데 s는 현재위치, n은 지금까지 방문한 노드들의 개수가 담긴다. 

3. n이 만약 ans보다 크다면 ans를 n으로 바꿔준다.

4. 모든 노드들을 확인하며 방문하지 않은 노드가 있다면 방문체크를 해주고 그 노드에 대해 dfs를 실행시켜준다. 

(단, dfs를 돌린후 다시 방문체크를 해야지 다음 경로때 다시 그 노드를 방문할 수 있게 된다)

 

def dfs(s, n):
    global ans
    if n > ans:
        ans = n

    for v in node[s]:
        if not visited[v]:
            visited[v] = 1
            dfs(v, n+1)
            visited[v] = 0

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    node = [[] for _ in range(N+1)]
    visited = [0] * (N+1)
    for _ in range(M):
        n1, n2 = map(int, input().split())
        node[n1].append(n2)
        node[n2].append(n1)

    ans = 0
    for i in range(1, N+1):
        visited[i] = 1
        dfs(i, 1)
        visited[i] = 0
    print('#{} {}'.format(tc, ans))