[백준 실버3] 2606 바이러스.py

<문제 설명>

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

2606번: 바이러스

컴퓨터의 연결정보와 컴퓨터가 몇 개인지에 대한 정보가 주어진다. 이때 1번 컴퓨터가 웜 바이러스에 감염되었다고 하자. 바이러스가 걸린 컴퓨터와 연결된 모든 컴퓨터가 웜 바이러스에 감염된다고 할때, 웜 바이러스에 걸린 컴퓨터가 총 몇 대인지를 반환하면 되는 문제이다.

 

입출력의 예는 다음과 같다.

예제 입력 1 

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1 

4

 

<문제 풀이 아이디어>

DFS 또는 BFS로 해결하면 되는 문제이고, 나는 DFS의 재귀 방식을 이용하여 문제를 해결했다.

우선 2차원 그래프를 통해 연결정보를 저장했고, 방문했는지를 나타내는 리스트를 통해 중복 방문 하지 않도록 했다.

DFS 함수를 만들고, 이를 재귀 호출하여 특정 노드와 연결된 모든 노드의 개수를 반환하도록 했고, 이를 cnt라는 전역변수에 저장해 최종적으로 출력하게 했다.

 

<문제 풀이 코드>

import sys

num1 = int(sys.stdin.readline())
num2 = int(sys.stdin.readline())
graph = [[]*num1 for _ in range(num1+1)] # 경로를 저장하기 위한 2차원 리스트
for _ in range(num2):
    a,b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

cnt = 0
visited = [0]*(num1+1) # 방문하지 않으면 0, 방문했으면 1

def dfs(start):
    visited[start] = 1
    global cnt
    for i in graph[start]:
        if visited[i]==0:
            dfs(i)
            cnt += 1
dfs(1)
print(cnt)

채점 결과