[PS] BOJ 2606 바이러스

문제 링크

📌 기본적인 DFS 문제

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리
   • 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼냄
3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복

def dfs(graph, v, visited):
    visited[v] = 1 # 방문 처리
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
    

n_nodes = int(input())
n_links = int(input())

# 각 노드가 연결된 정보를 2차원 리스트로 표현
graph = [[] for _ in range(n_nodes + 1)]
for _ in range(n_links):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a) # 양방향 연결

visited = [0] * (n_nodes + 1)

dfs(graph, 1, visited)
    
print(sum(visited) - 1) # 1번 컴퓨터 제외

양방향 연결하는 걸 잊지 말자...!