백준 2606 파이썬(DFS/BFS)

dfs/bfs문제다.

문제를 크게 꼬거나 어렵게 만들지 않은 것 같다.

dfs/bfs 둘중에 하나만 제대로 구현할 줄 알면 풀 수 있는 문제인 것 같다.

 

감염된 컴퓨터의 개수를 구하는 문제이므로

탐색문제에서는 시작점으로부터 방문한적이 있는 노드의 수를 카운팅하면 되는 문제이다.

 

BFS를 이용한 풀이

# 2606번 바이러스 - bfs

n = int(input())
m = int(input())
graph = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

visited = [0]*(n+1)

from collections import deque
def bfs(v):
    visited[v] = 1
    queue = deque()
    queue.append(v)
    while queue:
        node = queue.popleft()
        for i in range(n+1):
            if graph[i][node] == 1 and visited[i] == 0:
                queue.append(i)
                visited[i] = 1
bfs(1)

print(sum(visited)-1)

 

DFS를 이용한 풀이

# 2606번 바이러스 - dfs

n = int(input())
m = int(input())
graph = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

visited = [0]*(n+1)

def dfs(v):
    visited[v] = 1
    for i in range(n+1):
        if graph[i][v] == 1 and visited[i] == 0:
            dfs(i)
dfs(1)

print(sum(visited)-1)