[BOJ 2606] 바이러스

Depth First Search

[BOJ 2606] 바이러스

문제

구조화

• Node의(컴퓨터) 개수 n 정의
• 컴퓨터 간 관계의 수 m정의
• Node와 edge를 기준으로 그래프 생성
• 주의할 점은, 무방향 그래프이기에 양쪽 Edge를 모두 추가하는 형식으로 Graph 구현
• 방문 처리를 위한 State 생성
• 해당 문제는, 1번 노드를 통해 갈 수 있는 노드의 개수를 구하는 문제
• False형태의 state 생성
• 1번 노드로 부터 시작하여, 방문한 노드는 True 처리
• 재귀 종료 후 True의 개수를 Return
• 자기 자신인 1번 컴퓨터는 제외해야 하기에, True의 개수에서 -1

예제 시각화

해답

import sys
sys.setrecursionlimit(10**6)
n=int(input()) # 컴퓨터 수

graph = [[] for i in range(n+1)]
state = [False for i in range(n+1)] # 방문 처리
m=int(input()) # Edge 수

for i in range(m): # 그래프 구현
    a,b= map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(node): 
    state[node]=True # 방문 처리
    for nxt in graph[node]: 
        if state[nxt]==False: # 방문하지 않은 노드라면?
            dfs(nxt) # dfs
dfs(1)
print(state.count(True)-1) # 방문된 컴퓨터의 수에서 자기 자신인 1을 뺀 값을 출력