[SWEA] 2814. 최장 경로

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

SW Expert Academy

cycle이 존재하는 그래프의 DFS 탐색 문제이다. 한 정점의 탐색이 끝나면 visited 배열을 다시 0(방문 하지 않음)으로 바꿔주어야 하는 것이 포인트이다.

위와 같이 cycle이 있는 그래프가 있을 때 아래부터 일단 탐색을 한다고 친다.

우하단의 정점부터 시작해서 오른쪽 정점들을 계속 방문하며 방문 표시를 해준다. 더이상 방문할 점이 없기 때문에 다시 첫 정점으로 돌아간다.

새롭게 탐색을 시작하면 노란색으로 표시된 부분은 이미 방문했기 때문에 파란색으로 표시한 부분까지만 방문할 수 있게 된다. 그러면 해당 정점에서부터의 최장경로는 4가 된다.

그러나 실제 최장 경로는 위의 그림과 같이 정점을 방문하여 5가 되어야 한다. 이때문에, dfs를 이용해서 정점을 방문했다가 다시 되돌아올 때 방문표시를 바꿔주는 작업을 해야만 하는 것이다.

 

이를 빼면 일반 DFS와 똑같이 풀어주면 된다.

def dfs(v, cnt):
    global answer
    if cnt > answer:
        answer = cnt
    for nv in graph[v]:
        if not visited[nv]:
            visited[nv] = 1
            dfs(nv, cnt+1)
            visited[nv] = 0


for tc in range(1, int(input())+1):
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)
    answer = 0
    visited = [0] * (n + 1)
    for i in range(1, n+1):
        visited[i] = 1
        dfs(i, 1)
        visited[i] = 0
    print('#{} {}'.format(tc, answer))