[Baekjoon]백준 2606 바이러스(실버 3) - Python

문제설명 1

문제설명 2

문제를 살펴보면 연결된 컴퓨터 쌍을 보고 1번 컴퓨터를 통해 감염되는 컴퓨터 수를 구해야한다

해당 예제를 설명하기 위한 간단한 그림이 문제에 설명되어있는데, 이를 보면 그래프를 활용하는 것이

가장 간단할 것이라 생각하였다 연결 관계에 따라 탐색하기에 제일 적합한 구조이기 때문이다

 

일단 컴퓨터의 수, 컴퓨터 쌍의 수, 각 연결 정보를 입력받는 코드가 선행되어야한다

각 연결 정보를 저장하는 리스트가 추가로 필요한데, [a]의 위치에는 a와 연결된 컴퓨터가 저장되도록 해야한다

a, b를 입력받게된다면 graph[a].append(b), graph[b].append(a)가 실행되어야 양방향으로 정보가 저장된다

computer_num = int(input())
connection = int(input())
graph = [[] for i in range(computer_num+1)]
visited = [False] * (computer_num+1)
for _ in range(connection):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

이제 저장한 정보를 바탕으로 탐색을 해야하는데, bfs도 있지만 dfs로 구현해보았다

우선 방문여부를 확인하는 코드도 추가적으로 필요하다(위의 코드에서 미리 정의)

이후 탐색하는 위치의 값을 True로 변경하고 graph를 순회하면서 방문한 적이 없는 경우 dfs를 재귀적으로

호출함과 동시에 cnt 변수에 1을 더해주면된다

최종적으로 cnt 변수는 0으로 초기화하고 dfs(1)을 호출하게 되면 cnt에는 감염될 컴퓨터의 수가 저장될 것이다

(dfs(1)을 호출하는 이유는 문제에서 1번 컴퓨터를 통해 감염되는 컴퓨터의 수를 구해야하기때문)

import sys
input = sys.stdin.readline

def dfs(n):
    global cnt
    visited[n] = True
    for i in graph[n]:
        if not visited[i]:
            cnt += 1
            dfs(i)         

computer_num = int(input())
connection = int(input())
graph = [[] for i in range(computer_num+1)]
visited = [False] * (computer_num+1)
for _ in range(connection):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
cnt = 0
#print(graph)
dfs(1)
print(cnt)