[BOJ] 바이러스 - 2606 (S3)
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 128 MB |
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
풀이
이 문제는 그래프 탐색의 기본 문제로, 1번 노드에서 시작하여 연결된 모든 노드를 찾는 문제이다.
접근 방법
1번 컴퓨터와 연결된 모든 컴퓨터를 찾는 것은 그래프에서 연결 요소(Connected Component)를 찾는 것과 같다. DFS 또는 BFS를 사용하여 1번 노드에서 도달 가능한 모든 노드를 찾으면 된다.
핵심 아이디어
- 1번 컴퓨터부터 DFS/BFS 탐색 시작
- 방문한 컴퓨터를 체크하며 탐색
- 1번을 제외한 방문한 컴퓨터의 개수가 답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from collections import defaultdict
class Network:
def __init__(self, N, M):
self.N, self.M = N, M
self.cnt = 0
self.visited = [False] * (N + 1)
self.visited[1] = True
self.network = defaultdict(list)
self._make_network()
def _make_network(self):
for _ in range(self.M):
s, e = map(int, input().split())
self.network[s].append(e)
self.network[e].append(s)
def search_computer(self, node=1):
for n_node in self.network[node]:
if self.visited[n_node]:
continue
self.visited[n_node] = True
self.cnt += 1
self.search_computer(n_node)
def main():
N = int(input())
M = int(input())
network = Network(N, M)
network.search_computer()
print(network.cnt)
if __name__ == "__main__":
main()
코드 설명
Network 클래스
초기화 (__init__):
1
2
3
self.visited = [False] * (N + 1)
self.visited[1] = True # 1번은 이미 감염됨
self.network = defaultdict(list)
- 방문 배열 초기화
- 1번 컴퓨터는 이미 감염된 상태로 시작
defaultdict(list)로 그래프 구조 생성
네트워크 구성 (_make_network):
1
2
3
4
5
def _make_network(self):
for _ in range(self.M):
s, e = map(int, input().split())
self.network[s].append(e)
self.network[e].append(s)
- 양방향 그래프로 구성
- 각 컴퓨터의 연결 정보 저장
DFS 탐색 (search_computer):
1
2
3
4
5
6
7
def search_computer(self, node=1):
for n_node in self.network[node]:
if self.visited[n_node]:
continue
self.visited[n_node] = True
self.cnt += 1
self.search_computer(n_node)
- 재귀를 이용한 DFS 구현
- 방문하지 않은 인접 노드를 방문하며 카운트 증가
- 1번 노드는 이미 감염된 상태이므로 카운트에서 제외
시간 복잡도
- 그래프 구성: O(M)
- DFS 탐색: O(N + M)
- 전체 시간 복잡도: O(N + M)
N ≤ 100이므로 충분히 빠르게 해결할 수 있다.
다른 풀이 방법
BFS를 이용한 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import deque, defaultdict
N = int(input())
M = int(input())
graph = defaultdict(list)
for _ in range(M):
s, e = map(int, input().split())
graph[s].append(e)
graph[e].append(s)
visited = [False] * (N + 1)
visited[1] = True
q = deque([1])
cnt = 0
while q:
node = q.popleft()
for n_node in graph[node]:
if visited[n_node]:
continue
visited[n_node] = True
cnt += 1
q.append(n_node)
print(cnt)
BFS와 DFS 모두 동일한 결과를 얻을 수 있으며, 이 문제에서는 성능 차이가 거의 없다.
Union-Find를 이용한 풀이
Union-Find(Disjoint Set)를 사용하여 1번과 같은 집합에 속한 노드의 개수를 세는 방법도 가능하다.
주의 사항
- 1번 제외: 1번 컴퓨터는 이미 감염된 상태이므로 답에서 제외한다.
- 양방향 그래프: 네트워크는 양방향이므로 양쪽 모두 연결 정보를 저장한다.
- 방문 체크: 무한 루프를 방지하기 위해 방문 체크가 필수이다.
문제의 의의
이 문제는 그래프 탐색의 가장 기본적인 형태로, DFS/BFS의 개념을 이해하는 데 좋은 문제이다. 연결 요소를 찾는 기본 패턴을 익힐 수 있다.