SWEA 2814번 최장경로 (Python, DFS, D3)

SWEA 2814번 최장경로 문제 바로가기

문제 접근

경로의 최장길이를 구하는 문제이다. 그래프문제이기 때문에 DFS를 사용해서 풀어야겠다고 생각했다.
node의 시작점에 따라서 최장경로가 바뀌기 때문에 모든 node에서 한번씩 시작해보고 그중 가장 큰 값을 출력하면 된다.

문제 풀이

입력 처리

입력된 값을 2차원 배열에 넣어 연결되어 있음을 나타낸다.

N, M = map(int, input().split())
    node = [[] for i in range(N+1)]
    result = 0
    for i in range(M):
        x, y = map(int, input().split())
        node[x].append(y)
        node[y].append(x)

DFS

result라는 글로벌 변수를 설정하여 파라미터로 넘어간 cnt가 함수가 종료될 때(더 방문할 노드가 없을 때)result보다 크다면 result에 값을 저장한다.
따라서 최장경로는 result에 저장된다.

또한 dfs 재귀호출 후에 visited[현재노드]를 다시 미방문으로 처리하여 다른 경로상에서 또 방문할 수 있도록 해야 올바른 값이 나온다.

def dfs(x, cnt):
    global result
    visited[x] = 1
    for i in node[x]:
        if visited[i]==0:
            visited[i] = 1
            dfs(i, cnt +1)
    visited[x] = 0
    if cnt > result:
        result = cnt

제출 코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
def dfs(x, cnt):
    global result
    visited[x] = 1
    for i in node[x]:
        if visited[i]==0:
            visited[i] = 1
            dfs(i, cnt +1)
    visited[x] = 0
    if cnt > result:
        result = cnt
for test_case in range(1, T + 1):
    N, M = map(int, input().split())
    node = [[] for i in range(N+1)]
    result = 0
    for i in range(M):
        x, y = map(int, input().split())
        node[x].append(y)
        node[y].append(x)
    for i in range(1, N+1):
        visited = [0 for _ in range(N+1)]
        dfs(i,1)
    print(f'#{test_case} {result}')