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

1. 문제와 예제

(문제 링크: https://www.acmicpc.net/problem/2606)

2606번: 바이러스

문제

예제

---

2. 전체 코드

1) BFS

# BFS
from collections import deque
import sys
input = sys.stdin.readline

# 입력 받기
N = int(input().rstrip()) # 컴퓨터 개수
V = int(input().rstrip()) # 연결된 컴퓨터 쌍 개수

lst = [[] for i in range(N+1)] # 연결 정보 리스트
virus = [0] * (N+1) # 각 컴퓨터가 바이러스에 걸렸는지 여부 리스트

# 연결 정보 리스트 생성
# ex. lst = [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
for i in range(V):
    a, b = map(int, input().split()) # 연결되어 있는 컴퓨터 번호 쌍
    lst[a] += [b] # a에 b 연결
    lst[b] += [a] # b에 a 연결

virus[1] = 1 # 1번 컴퓨터는 감염
deq = deque([1]) # 큐 생성

while deq:
    num = deq.popleft() # num은 감염
    for i in lst[num]: # num에 연결된 i들에 대해
        if virus[i] == 0: # 감염되어 있지 않다면
            deq.append(i) # 다음 과정에서 i에 연결된 컴퓨터들을 확인하기 위해 큐에 추가
            virus[i] = 1 # i는 감염

# 결과 출력하기
print(sum(virus)-1) # 개수에서 1번 컴퓨터는 제외

 

2) DFS

# DFS
import sys
input = sys.stdin.readline

# 입력 받기
N = int(input().rstrip()) # 컴퓨터 개수
V = int(input().rstrip()) # 연결된 컴퓨터 쌍 개수

lst = [[] for i in range(N+1)] # 연결 정보 리스트
virus = [0] * (N+1) # 각 컴퓨터가 바이러스에 걸렸는지 여부 리스트

# 연결 정보 리스트 생성
# ex. lst = [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
for i in range(V):
    a, b = map(int, input().split()) # 연결되어 있는 컴퓨터 번호 쌍
    lst[a] += [b] # a에 b 연결
    lst[b] += [a] # b에 a 연결

def dfs(v):
    virus[v] = 1 # v는 감염
    for i in lst[v]: # v에 연결된 i들에 대해
        if virus[i] == 0: # 감염되어 있지 않다면
            dfs(i) # i부터 시작해서 바이러스 감염

dfs(1) # 1번 컴퓨터부터 바이러스 시작

# 결과 출력하기
print(sum(virus)-1) # 개수에서 1번 컴퓨터는 제외

 

---

3. 코드 해설

반드시 알아야 하는 BFS, DFS 개념이다. BFS로 풀리는 문제는 DFS로도 풀리고, 반대도 마찬가지다. 이 둘의 개념은 아래 게시글에서 자세히 살펴보자. https://yunyoung1819.tistory.com/86

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

1번 풀이가 왜 BFS(너비 우선 탐색)인지 설명하자면, 1번 컴퓨터로 시작해서 1번 컴퓨터에 연결된 모든 컴퓨터들 중 한 컴퓨터에 연결된 컴퓨터들을 deq에 추가해놓고, 1번 컴퓨터에 연결된 다른 한 컴퓨터에 연결된 컴퓨터들에 대해 과정을 반복한다. 해당 과정들이 끝나면 deq에 추가한 순서대로 deq.popleft()를 진행하기 때문에 순서가 BFS와 동일하다.

 

2번 풀이가 왜 DFS(깊이 우선 탐색)인지 설명하자면, dfs(1)로 시작해서 1번 컴퓨터에 연결된 한 컴퓨터에 대해 dfs(i)가 시작되어 dfs(i) 안에서 i에 연결된 한 컴퓨터에 대해 또 다른 dfs(i)가 진행될 것이므로 순서가 DFS와 동일하다.