[백준 2606번-바이러스]-파이썬

<문제>

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

<풀이>

1.각 컴퓨터의 방문여부를 저장하는 배열(visited)을 선언한다.

2.-DFS풀이법-

 

2-1. 1번에서 출발하므로 visited[1]에 방문을 체크한다.

2-2. 1번과 연결되어있는 컴퓨터로 이동해 방문 여부를 확인한다.

2-3. 방문하지 않은 경우 바이러스를 확산시키고(count+=1) DFS 함수를 재귀적으로 호출한다.

2-4. 연결되어 있는 노드가 이미 방문이 된경우 연결되어있는 다른 노드로 이동한다.

2-5. 1번과 연결되어있는 모든 노드가 방문된 경우 종료된다.

 

 

3.-BFS풀이법-

 

3-1. 1번에서 출발하므로 큐에 1을 삽입한다.

2-2. 1번을 큐에서 추출하고 1번에 방문표시를 한다.

2-3. 큐에서 추출된 컴퓨터와 연결된 모든 컴퓨를 큐에 삽입하고 큐에서 원소를 하나씩 추출한다.

2-4. 추출된 원소가 방문되어있지 않은 경우 방문표시를 하고 바이러스에 감염시킨다(count+=1). 

2-5. 큐에서 추출된원소와 연결된 모든 컴퓨터를 큐에 삽입한다.

2-6. 큐가 빌때까지 위 2-3번~2-5번 과정을 반복한다.

 

 

 

 

<코드>-파이썬

-DFS풀이법-

import sys
n = int(sys.stdin.readline()) #컴퓨터의 갯수
k = int(sys.stdin.readline()) #연결된 쌍의 갯수
graph = [[] for _ in range(n+1)]
for i in range(k):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
count = 0
visited = [False]*(n+1)
#DFS 알고리즘
def dfs(x):
    global count
    visited[x] = True
    for i in graph[x]:
        if not visited[i]:
            count+=1
            dfs(i)

dfs(1)
print(count)

-BFS풀이법-

from collections import deque
import sys
n = int(sys.stdin.readline()) #컴퓨터의 갯수
k = int(sys.stdin.readline()) #연결된 쌍의 갯수
graph = [[] for _ in range(n+1)]
for i in range(k):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
count = 0
visited = [False]*(n+1)
#BFS 알고리즘
def bfs(x):
    global count
    queue = deque()
    queue.append(x)
    while queue:
        a = queue.popleft()
        visited[a] = True
        for i in graph[a]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                count+=1
    return count
print(bfs(1))