SWEA: 2814 최장 경로

문제

SW Expert Academy

 

문제 풀이

 주어진 입력 값 N, M에 따라 간선 정보를 토대로 그래프를 초기화 해준 후 각 노드마다 연결된 노드들로 경로를 탐색하면 된다. 이때 백트랙킹이 필요하므로 `DFS`로 탐색을 진행하여 연결된 노드의 개수가 크면 갱신시켜주면 문제를 해결할 수 있다.

 

코드

from collections import defaultdict


T = int(input())


def dfs(cur_node, cnt):
    global answer

    if answer < cnt:
        answer = cnt

    for next_node in graph[cur_node]:
        if not visited[next_node]:
            visited[next_node] = True
            dfs(next_node, cnt + 1)
            visited[next_node] = False


for test_case in range(1, T + 1):
    answer = 0
    n, m = map(int, input().split())
    graph = defaultdict(list)
    visited = [False] * (n + 1)

    for _ in range(m):
        node, other_node = map(int, input().split())
        # 그래프는 양방향 성이므로 2방향 모두 추가
        graph[node].append(other_node)
        graph[other_node].append(node)

    # 시작 노드를 다르게 하여 DFS로 노드들을 탐색함
    for node in range(1, n + 1):
        visited[node] = True
        dfs(node, 1)
        visited[node] = False

    print('#' + str(test_case), answer)

 백트랙킹에서는 항상 주의하여, 특정 가지에서 `visited`를 `True`로 하였다면 호출 스택에서 복귀 후에 다시 `False`로 만들어 백트랙킹이 가능하도록 하여야 한다.