[백준] 2606번 : 바이러스 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2606번: 바이러스

 

1. 문제 설명

2. 풀이과정

1. 해당 문제는 그래프 탐색을 활용하여 해결할 수 있다.
2. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
3. 깊이 우선 탐색을 활용하여 해결하였다. 깊이 우선 탐색을 수행하는 함수를 생성한다. def Search(start)
4. 해당되는 정점을 탐색한 것으로 표시한다. result[start] = True
5. 해당 정점과 연결되는 정점들을 하나씩 추출한다. for i in graph[start]
6. 만약 추출한 정점이 아직 탐색하지 않은 정점이라면 if (not result[i])
7. 해당 정점에서 깊이 우선 탐색을 새로 시작한다. Search(i)
8. 먼저 컴퓨터의 수를 입력받는다. N = int(sys.stdin.readline())
9. 연결되어 있는 컴퓨터 쌍의 수를 입력받는다. M = int(sys.stdin.readline())
10. 각 연결을 그래프로 나타내기 위해 리스트를 생성한다. graph = list()
11. 리스트는 각 컴퓨터가 어떤 컴퓨터와 연결되어 있는지 정보를 저장한다. for _ in range(N): graph.append([])
12. 컴퓨터 쌍의 수만큼 반복하며 for i in range(M)
13. 서로 연결된 컴퓨터 번호를 입력받고 v1, v2 = map(int, sys.stdin.readline().split())
14. 그래프로 저장한다. 컴퓨터 번호는 1번부터 시작하지만 그래프로 저장하는 리스트는 0번부터 인덱스 번호가 시작되므로 이를 고려하여 저장한다. graph[v1 - 1].append(v2 - 1)  graph[v2 - 1].append(v1 - 1)
15. 그래프를 오름차순으로 정렬한다. for i in graph: i.sort()
16. 그래프 탐색을 할 때 해당 컴퓨터를 탐색했는지 나타내줄 리스트를 생성하고 각 컴퓨터 번호를 False로 초기화한다. result = [False] * N
17. 컴퓨터 번호 1번, 인덱스 번호 0번부터 탐색을 시작하여 감염된 컴퓨터를 파악한다. Search(0)
18. 시작 컴퓨터인 1번을 제외하고 몇 개의 컴퓨터가 감염되었는지 세어 출력한다. print(result.count(True) - 1)

반응형

3. 소스코드

import sys

def Search(start):
    result[start] = True
    
    for i in graph[start]:
        if (not result[i]):
            Search(i)

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

graph = list()
for _ in range(N):
    graph.append([])

for i in range(M):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1 - 1].append(v2 - 1)
    graph[v2 - 1].append(v1 - 1)

for i in graph:
    i.sort()

result = [False] * N
Search(0)

print(result.count(True) - 1)