또 테스트 케이스 오버피팅 ,,,

1. 내 풀이: 실패

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)

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

cnt = 0
freind = 0
def dfs(x):
    global cnt
    global freind
    visited[x] = 1
    if len(graph[x]) == 0:
        print(freind)
        return
    if cnt == 3:
        print(freind)
        return
    cnt += 1
    for i in graph[x]:
        if visited[i] == 0:
            visited[i] = 1
            freind += 1
            dfs(i)
            
dfs(1)

이렇게 풀면 테스트 케이스만 통과 ^^ ...

2. 다른 풀이

import sys
from collections import defaultdict, deque

def bfs(start):
    cnt = 0
    visited = [0 for _ in range(n+1)]
    visited[start] = 1
    queue = deque([[start, 0]])
    while queue:
        u, dist = queue.popleft()
        if dist <= 2: # 친구의 친구(dist==2)까지 초대할 수 있다
            cnt += 1
        for v in g[u]:
            if not visited[v]:
                visited[v] = 1
                queue.append([v, dist+1])
    return cnt-1 # cnt에 자기 자신까지 포함되어 있으므로 1을 빼준다

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
g = defaultdict(list)
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    g[a].append(b)
    g[b].append(a)

print(bfs(1))

풀이 출처: https://cotak.tistory.com/132

deque에 2개나 넣을 수 있는 지 처음 알았다 ㅎㅎ ...
하긴 또 생각해보면 못 넣을 건 없지.
나처럼 global 변수 쓰지말고 이런 식으로 처리하는 게 더 좋은 것 같다.

3. 마치며

그래프 자신감 잃어가는 중 ...
실버로 양치기 해보자!