[백준] 2606 바이러스 - python

백준 실버3 2606 바이러스 python

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

2606번: 바이러스

---

문제 이해

---

코드

맞았습니다가 뜬 코드입니다. - 메모리31256 KB | 시간 68ms | 코드 길이 431B

DFS (깊이 우선 탐색)

import sys
C = int(sys.stdin.readline().rstrip())
N = int(sys.stdin.readline().rstrip())
graph = [[] for i in range(C+1)]
visited = [0] * (C+1)
visited[1] = 1
for _ in range(N):
    com1, com2 = map(int, sys.stdin.readline().rstrip().split())
    graph[com1] += [com2]
    graph[com2] += [com1]
def dfs(com):
    visited[com] = 1
    for c in graph[com]:
        if visited[c] == 0:
            dfs(c)
dfs(1)
print(sum(visited)-1)

이중 리스트 graph로 컴퓨터 간의 연결을 저장해줍니다. 만약 1 2 입력이 들어왔다면 graph의 1번째 인덱스에 해당하는 리스트에 2을 넣고, 2번째 인덱스에는 1을 넣어줍니다.

visited 리스트에는 바이러스에 걸렸는지에 대한 여부를 저장합니다. (1은 걸림, 0은 안 걸림)

dfs는 깊이 우선 탐색 함수를 구현합니다. 인자로 들어온 수에 해당하는 visited의 인덱스에 1을 넣습니다. 그리고 graph[com] 안의 모든 요소(graph[com]과 연결된 요소들)를 확인하여 visited리스트에 해당 리스트가 0일 경우, dfs를 호출해서 1을 넣고 다시 확인하는 작업을 해줍니다.

 

BFS (넓이 우선 탐색)

import sys
from collections import deque
C = int(sys.stdin.readline().rstrip())
N = int(sys.stdin.readline().rstrip())
graph = [[] for i in range(C+1)]
visited = [0] * (C+1)
visited[1] = 1
for _ in range(N):
    com1, com2 = map(int, sys.stdin.readline().rstrip().split())
    graph[com1] += [com2]
    graph[com2] += [com1]
Q = deque([1])
while Q:
    com = Q.popleft()
    for c in graph[com]:
        if visited[c] == 0:
            Q.append(c)
            visited[c] = 1
print(sum(visited)-1)

Q = deque([1])로 첫번째 컴퓨터에 대한 덱을 만듭니다. while문에서 Q의 맨 왼쪽 요소를 pop하여 com에 넣고, com에 해당하는 graph의 인덱스를 확인합니다. 만약 그 인덱스의 visited리스트가 0이라면, Q에 c를 넣고 visited에는 1을 저장합니다.

 

---

Try 1.

틀렸습니다가 뜬 코드입니다. - 코드 길이 309B

import sys
C = int(sys.stdin.readline().rstrip())
N = int(sys.stdin.readline().rstrip())
com = [0] * (C+1)
com[1] = 1
for _ in range(N):
    com1, com2 = map(int, sys.stdin.readline().rstrip().split())
    if com[com1] == 1 or com[com2] == 1:
        com[com1] = 1
        com[com2] = 1
print(com.count(1)-1)

• 연결쌍이 순서대로 입력되지 않은 경우를 놓쳤습니다.
  예를 들어, 1 2 -> 3 4 -> 2 3 으로 입력이 들어온다면, 3과 4의 연결을 놓치게 됩니다.

---

Search 🔍

• 구글링한 코드입니다. 출처 : https://bio-info.tistory.com/152