[백준] 2606 파이썬(python) : 바이러스

2606번 : 바이러스

 

 

 

나의 풀이(dfs)

import sys
n = int(input())
m = int(input())
graph = [ [] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visit = [0] * (n+1) #1
cnt = 0
def dfs(v):
    global cnt
    visit[v] = 1
    for i in graph[v]:
        if visit[i] == 0:
            cnt += 1
            dfs(i)
dfs(1) #2
print(cnt)

 

 

dfs로 문제를 해결했다. 하지만 bfs로 해결하는 방법도 있다. 

#1 : dfs에 빠지면 안되는 방문표시

#2 : 모든 노드는 1에서 시작한다했으니 dfs(1)로 실행

 

 

나의 풀이(bfs)

from collections import deque
import sys
n = int(input())
m = int(input())
graph = [ [] for _ in range(n+1) ]
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visit = [0] * (n+1)
cnt = 0
def bfs():
    q = deque()
    q.append(1) #1
    visit[1] = 1 #2
    global cnt
    while q:    
        v = q.popleft()
        for i in graph[v]:
            if visit[i] == 0:
                cnt += 1
                visit[i] = 1
                q.append(i)
bfs()
print(cnt)

 

 

#1 : 1에서부터 시작이니까 q에 1추가

#2 : 첫노드 방문처리

 

 

아래가 dfs, 위는 bfs로 제출

 

 

같은 문제지만 bfs와 dfs로 풀어볼 수 있는 문제입니다. 같은 문제도 다르게 풀 수 있어서 좋았습니다.