📌난이도🥈

📌코드

import sys
input = sys.stdin.readline



T = int(input())


def dfs(start, count): # 

    visited[start] = 1
    for i in graph[start]:
        if visited[i] == 0:
            visited[i] = 1
            count = dfs(i, count+1)
    return count


for i in range(T):
    case = dict()
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    for j in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    visited = [0]*(N+1)

    result = dfs(1, 0)
    print(result)

📌후기

어우... 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다. 이 조건을 많이 신경쓰지 않았었다. 이 조건이 있을때 없을때는 난이도 차이가 엄청나는 것 같다.

📘없을 때...

[[], [2, 3], [1, 3], [2, 1]]
[[], [2], [1, 3], [2, 4], [3, 5], [4]]

이러한 형태에서 재귀를 쓰려하면 같은 곳을 무수히 반복할 수 있는 경우를 어떻게 나누는지 몰라 매우 당황했다. ( 1-2-1-2-1-2.....) 이런 경우들을 구별해야한다는 것.. 결국 못풀었다

그런데!!!!!!!!!

📘있다면

문제를 계속 읽다가 저게 뭔소린가 해서 그림을 그려보았더니 ㅋㅋㅋㅋㅋ 노드들이 무조건 n-1번에 끝나게 된다는 것 이었다.... 위에서 복잡하게 생각했던 문제가 시간낭비가 되었던 것이다. 그렇다면 임의의 점을 하나 정해서 최대 깊이가 n-1 일 때 무조건 끝나게 되어있다...