[DFS/BFS] BOJ 2606 - 바이러스 / python
문제링크
https://www.acmicpc.net/problem/2606
문제
입출력
💡 사고의 흐름
- 컴퓨터가 연결된 구조 -> graph
- 1번 컴퓨터가 무조건 웜 바이러스에 걸림 -> 1번부터 탐색하면 됨.
- graph 는 n x n 크기 (1번부터 n번까지니까 1, n+1로 탐색!)
- 주어진 노드 수만큼 graph에 1로 마킹을 하고, check 리스트를 두어 탐색한다.
- 탐색한 만큼 cnt+=1를 해주어 감염된 컴퓨터(1번 제외) 수를 카운팅한다.
Code (DFS)
import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = [[0 for _ in range(N+1)] for _ in range(N+1)]
check = [0] *(N+1)
cnt = 0
def dfs(node):
global cnt
check[node]= True
for i in range(1,N+1):
if graph[node][i] == 1 and check[i]==False:
cnt+=1
dfs(i)
return cnt
for i in range(M):
a, b = map(int, sys.stdin.readline().split())
graph[a][b]=1
graph[b][a]=1
print(dfs(1))
Code (BFS)
import sys
from collections import deque
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph=[[0 for _ in range(n+1)] for _ in range(n+1)]
check=[False for _ in range(n+1)]
def bfs(x):
cnt=0
q = deque()
check[x]=True
q.append(x)
while q:
tmp =q.popleft()
for i in range(1,n+1):
if graph[tmp][i] ==1 and check[i]==False:
q.append(i)
check[i]=True
cnt+=1
return cnt
if __name__=='__main__':
for _ in range(m):
a,b = map(int, sys.stdin.readline().split())
graph[a][b]=1
graph[b][a]=1
print(bfs(1))
+) 수정 2/9
Author And Source
이 문제에 관하여([DFS/BFS] BOJ 2606 - 바이러스 / python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jiyeon0410/DFS-BOJ-2606-바이러스-python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)