백준 - 바이러스

설명

• DFS, 스택 이용
• 입력으로 들어오는 그래프 연결 정보를 인접 리스트로 만든다.
• 1번 컴퓨터와 연결된 컴퓨터들의 개수만 찾으면 된다.

풀이

n = int(input()) # 컴퓨터의 수
pair = int(input()) # 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수

graph = { key + 1 : [] for key in range(n) }
for i in range(pair):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(start_v):
    discovered = []
    stack = [start_v]
    cnt = 0

    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            cnt += 1
            for w in graph[v]:
                stack.append(w)
    return cnt - 1

print(dfs(1))