[SWEA] 2814. 최장 경로

2814. 최장 경로

기존에 틀린 풀이

• 각 정점의 visited 에서 가장 큰 값을 비교해 출력하였는데, 10개 중에 6개만 정답이었다.

t = int(input())

for k in range(1, t + 1):
    n, m = map(int, input().split())

    # 정점 개수 : n / 간선 개수 : m
    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        graph[a].sort()
        graph[b].sort()


    def dfs(v):

        for i in graph[v]:
            if not visited[i]:
                visited[i] = visited[v] + 1
                dfs(i)


    ans = 0
    visited = [0] * (n + 1)
    for a in range(1, n + 1):
        visited[a] = 1
        dfs(a)
        ans = max(max(visited), ans)
        visited[a] = 0

    print(f"#{k} {ans}")

문제 풀이

• dfs 함수에 cnt를 넣어 구현하였다.
• 가장 깊게 들어갔을 때 cnt가 가장 큰 값을 가지는데, 각 노드에서 출발해 cnt 값 중 가장 큰 값을 출력한다.

t = int(input())

for k in range(1, t + 1):
    n, m = map(int, input().split())

    # 정점 개수 : n / 간선 개수 : m
    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        graph[a].sort()
        graph[b].sort()


    def dfs(v, cnt):
        global ans
        ans = max(cnt, ans)
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                dfs(i, cnt + 1)
                visited[i] = False


    ans = 0
    visited = [0] * (n + 1)
    for a in range(1, n + 1):
        visited[a] = True
        dfs(a, 1)
        visited[a] = False

    print(f"#{k} {ans}")