[코딩테스트] 2606번, 바이러스

Clean Code Big Poo·2024년 8월 1일

코딩테스트

목록 보기

1/4

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

입력 예시

7 # 컴퓨터 수
6 # 컴퓨터 쌍
1 2 # 여기부터 연결된 컴퓨터 번호 쌍 입력
2 3
1 5
5 2
5 6
4 7

문제 설명

문제 요약

N대의 컴퓨터가 있고, 각 컴퓨터는 1번부터 N번까지 번호가 매겨져있다.
M개의 직접 연결된 컴퓨터 쌍이 주어진다.
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 이 바이러스가 퍼질 수 있는 모든 컴퓨터의 수를 구하기

입력 형식

첫 번째 줄: 컴퓨터의 수 ( N ) (1 ≤ ( N ) ≤ 100)
두 번째 줄: 네트워크 상에서 직접 연결된 컴퓨터 쌍의 수 ( M )
다음 ( M )개의 줄: 두 개의 정수 ( a )와 ( b ), 이는 ( a )번 컴퓨터와 ( b )번 컴퓨터가 연결되어 있다는 의미

출력 형식

1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수를 출력

문제 풀이 방법

문제 풀이 과정

그래프 표현: 컴퓨터 네트워크를 인접 행렬을 사용하여 그래프로 표현
DFS 탐색: 깊이 우선 탐색(DFS)를 사용하여 1번 컴퓨터와 연결된 모든 컴퓨터를 탐색

왜 DFS 탐색을 사용할까? 참고
DFS는 재귀적으로 깊이 들어가면서 탐색하는 방식이다. 주어진 문제는 1번 컴퓨터와 연결된 모든 컴퓨터를 탐색하여 바이러스가 퍼질 수 있는 컴퓨터의 수를 구하는 것이므로 (BFS 알고리즘도 사용 할 수 있지만) DFS 를 사용한다. BFS 는 최단 거리 구하기에 유리하다.
감염된 컴퓨터 수 계산: 1번 컴퓨터를 통해 감염될 수 있는 모든 컴퓨터를 세어 출력

코드

n = int(input())  # 컴퓨터의 수 입력
m = int(input())  # 네트워크 상에서 직접 연결된 컴퓨터 쌍의 수 입력

# 인접 리스트 초기화
graph = [[] for _ in range(n)]
visited = [False] * n # 1번부터 n 번 컴퓨터의 방문 여부

# 연결된 컴퓨터 쌍 정보 입력
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

print(grape)

def dfs(v):
    visited[v] = True # 현재 컴퓨터 방문 처리
    count = 1
    for neighbor in graph[v]:
        if not visited[neighbor]:
            count += dfs(neighbor)
    return count # 감염된 컴퓨터 개수

# 1번 컴퓨터에서 시작하므로 0번 인덱스에서 시작
result = dfs(0) - 1
print(result)

출력

# grape
[[1, 4], [0, 2, 4], [1], [6], [0, 1, 5], [4], [3]] 
# 바이러스 감염된 컴퓨터 수
4

graph = [
    [1, 4],    # 1번 컴퓨터는 2번, 5번 컴퓨터와 연결
    [0, 2, 4], # 2번 컴퓨터는 1번, 3번, 5번 컴퓨터와 연결
    [1],       # 3번 컴퓨터는 2번 컴퓨터와 연결
    [6],       # 4번 컴퓨터는 7번 컴퓨터와 연결
    [0, 1, 5], # 5번 컴퓨터는 1번, 2번, 6번 컴퓨터와 연결
    [4],       # 6번 컴퓨터는 5번 컴퓨터와 연결
    [3]        # 7번 컴퓨터는 4번 컴퓨터와 연결
]

코드의 상세 설명

입력 처리
- n: 컴퓨터의 수
- m: 네트워크 상에서 직접 연결된 컴퓨터 쌍의 수
- 인접 행렬 graph를 초기화합니다. graph[v]에 연결된 컴퓨터 정보 담기
- visited는 방문 여부를 체크하는 리스트로, visited[i]가 1이면 i번 컴퓨터를 방문한 것
네트워크 연결 정보 입력
- 각 컴퓨터 쌍을 입력 받아 인접 행렬 graph에 저장. 컴퓨터 번호는 1부터 시작하지만, 인덱스는 0부터 시작하므로 a-1과 b-1을 사용
DFS 함수
- dfs(v)는 v번 컴퓨터를 방문하여 연결된 모든 컴퓨터를 탐색
- 현재 컴퓨터 v를 방문 처리 (visited[v] = True).
- 모든 컴퓨터를 순회하며,visited[neighbor]가 False인 경우에만 탐색(재귀)
- count는 감염된 컴퓨터 개수를 세는 변수
결과 출력
- dfs(0)을 호출하여 1번 컴퓨터(0번 인덱스)를 시작점으로 감염된 컴퓨터 수를 계산하여 출력

Clean Code Big Poo

다음 포스트

[코딩테스트] 2606번, 바이러스