[Python, 파이썬] SWEA 2814. 최장 경로

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

 

 

def DFS(i, now):

    global all_max

    if(now > all_max):
        all_max = now

    for child in graph[i]:
        if not depth[child]: # 방문하지 않았을 시

            depth[child] = True
            DFS(child, now+1) # 자식 노드로 이동
            depth[child] = False # 백트래킹
              

T = int(input()) # 테스트케이스 수 T

for test_case in range(1, T+1):

    N, M = map(int, input().split()) # 자연수 N, M
    graph = [[] for _ in range(N+1)] # 인접 리스트

    for i in range(M):
        s, e = map(int, input().split()) # 간선 입력받기
        
        graph[s].append(e)
        graph[e].append(s)

    all_max = 0 # 모든 최장 경로

    # 최장 경로 길이 계산
    for i in range(1, N+1):
        depth = [False]*(N+1) # 방문 여부 저장 배열
        depth[i] = True # 시작하는 노드를 방문 처리
        DFS(i, 1) # 탐색 시작
            
    print("#%d %d" %(test_case, all_max))    

 

 

 

 

 

[문제풀이]

---

 

그래프의 최장 경로를 계산해야 하는데, 어떤 정점에서 시작하는지 딱 집어지지 않았으므로 모든 정점에서의 각 경로를 계산해서 그 중 최장 경로를 찾아야 한다.

 

보통 모든 정점 쌍의 경로는 플로이드 워셜을 쓰지만 여기선 불가능!

왜냐면, 한번 간 경로는 갈 수 없기 때문인데, 플로이드는 그런 제약을 걸 수 없다.

그래서 DFS로 탐색해야 하는데 여기서 그냥 DFS를 쓸 수는 없다.

 

 

이렇게 사이클이 있는 그래프의 경우 DFS로 탐색할 때 문제가 발생한다.

최장 경로 : 1 - 2 - 3 - 7 - 4 - 5 - 6

 

1 - 2 - 3 이후 이동할 수 있는 노드는 4 or 7이다.

그런데 여기서 4로 먼저 이동하게 되면 4를 방문체크를 하여 1 - 2 - 3 - 7 - 4 경로가 불가능해진다.

즉, 사이클이 있으면 한 노드를 먼저 방문 시 다음번 노드를 방문할 수가 없어진다.

 

if not depth[child]: # 방문하지 않았을 시
    depth[child] = True
    DFS(child, now+1) # 자식 노드로 이동
    depth[child] = False # 백트래킹

 

그래서 이렇게 백트래킹을 사용해서 DFS로 풀어줘야 모든 경로를 다 확인할 수 있다.