백준 - 2606 바이러스

2606 바이러스[실버 3]

오랜만이라서 싹 다 까묵음...

공부하는김에 DFS와 BFS, 두 방식으로 풀어볼게요

---

BFS

from collections import  deque
N = int(input())
M = int(input())
graph = list([] for _ in range(N+1))
visitChk = [False] * (N+1)

for _ in range(M) :
    i, j = map(int,input().split())
    graph[i].append(j)
    graph[j].append(i)

def bfs(start) :
    dq = deque([start])
    while dq :
        now = dq.popleft()
        visitChk[now]  = True
        for j in graph[now] :
            if not visitChk[j] :
                dq.append(j)
    count = 0;
    for i in visitChk :
        if i :
            count = count + 1
    print(count-1)
bfs(1)

BFS에서 중요한 deque !

def bfs(start) :
    dq = deque([start])
    while dq :
        now = dq.popleft()
        visitChk[now]  = True
        for j in graph[now] :
            if not visitChk[j] :
                dq.append(j)

이 부분이 BFS를 하는 부분이다

---

DFS

N = int(input())
M = int(input())
graph = list([] for _ in range(N+1))
visitChk = [False] * (N+1)

for _ in range(M) :
    i, j = map(int,input().split())
    graph[i].append(j)
    graph[j].append(i)

def dfs(now) :
    visitChk[now] = True
    for j in graph[now] :
        if not visitChk[j] :
            dfs(j)

dfs(1)

count = 0
for i in visitChk:
    if i:
        count = count + 1
print(count - 1)

DFS는 재귀호출을 이용하여 BFS보다 비교적 간단하게 구현 가능하다

def dfs(now) :
    visitChk[now] = True
    for j in graph[now] :
        if not visitChk[j] :
            dfs(j)