이번 문제는 DP와 BFS를 활용하여 해결하였다. 문제를 해석하면 현재 노드에서 다음 노드를 결정할 때, 현재 노드와 연결된 갯수보다 다음 노드와 연결된 갯수가 더 많아야 한다. 이 중 가장 많이 이동할 수 있는 경우의 수를 구하는 문제이다.

이 문제를 DP로 해결한 이유는 하나의 노드에서 출발하여 갈 수 있는 최대값을 구했을 때, 그 노드를 지난다면 그 뒤의 경로는 미리 구한 결과와 같기 때문에 각 노드에서 출발하여 갈 수 있는 최대 갯수를 저장해둔다면 이를 바로 이용할 수 있을 것이라 생각했기 때문이다.

그래서 BFS를 통해 탐색하며 만약 다음 노드의 연결 갯수가 현재 노드의 연결 갯수보다 많을 때, 다음 노드의 경로 최대값이 구해져있다면, 결과 변수를 다음 노드의 경로와 현재까지의 경로 길이를 더한 값과 결과 변수 중의 큰 값으로 취하도록 하였다. 만약 다음 노드의 경로 최대값이 구해져있지 않다면 큐에 담아 탐색을 계속해서 진행하도록 하였다. while문이 종료되면 dp[start]를 결과 변수로 갱신해주었다. 결과적으로 답은 dp리스트의 최댓값이 된다.

Code

from collections import deque
n, m = map(int, input().split())
links = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    links[a].append(b)
    links[b].append(a)
dp = [0 for _ in range(n)]
def get_map(start):
    q = deque()
    q.append((start, 1))
    result = 0
    while q:
        cur, cnt = q.popleft()
        result = max(result, cnt)
        for nxt in links[cur]:
            if len(links[nxt]) > len(links[cur]):
                if dp[nxt]:
                    result = max(result, dp[nxt]+cnt)
                else:
                    q.append((nxt, cnt+1))
    dp[start] = result
for start in range(n):
    get_map(start)
print(max(dp))