| 시간 제한 | 메모리 제한 |
|---|---|
| 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번을 제외한 방문한 컴퓨터의 개수가 답
코드
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__):
self.visited = [False] * (N + 1)
self.visited[1] = True # 1번은 이미 감염됨
self.network = defaultdict(list)- 방문 배열 초기화
- 1번 컴퓨터는 이미 감염된 상태로 시작
defaultdict(list)로 그래프 구조 생성
네트워크 구성 (_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)- 양방향 그래프로 구성
- 각 컴퓨터의 연결 정보 저장
DFS 탐색 (search_computer):
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를 이용한 풀이
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의 개념을 이해하는 데 좋은 문제이다. 연결 요소를 찾는 기본 패턴을 익힐 수 있다.