[Python]Baekjoon 2606번: 바이러스(DFS)

1. 문제

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

2606번: 바이러스

저번에 풀었던 문제이다.

지난번 포스팅 링크:

https://daily-stack.tistory.com/70

[Python]Baekjoon 2606번: 바이러스(BFS)

1번 컴퓨터와 연결된 컴퓨터가 몇 개인지를 구하는 문제이다.

그래프 탐색 문제이다.

2. 풀이

이번에는 DFS를 이용하여 풀이해 보자.

지난 포스팅에서 배웠던 대로 재귀함수를 이용하여 풀이할 것이다.

컴퓨터와 네트워크를 입력받고 그래프를 구성하는 과정은 이전과 동일하다.

dfs라는 함수를 재귀적으로 호출하여 DFS 탐색을 수행한다.

dfs 함수를 살펴보면, 방문할 컴퓨터의 번호를 매개변수 v로 전달받는다.

v에 방문했으므로 visited[v]를 1로 변경해 주고, for문과 graph[v]를 통해 v에 연결된 컴퓨터에 방문한다.

연결된 컴퓨터의 visited를 검사하여 방문하지 않은 컴퓨터라면 dfs(node) 재귀 호출을 통해 해당 컴퓨터를 방문하고 이 과정을 반복한다.

방문했던 컴퓨터라면 아무일도 잃어나지 않고 그 함수가 종료(스택에서 빠져나옴) 된다.

여기서 dfs 함수에 visited를 인자로 입력받지도 않고, return 하지도 않았는데 어떻게 print(sum(visited)-1)이 정답이 될 수 있는지 궁금할 수 있다.

파이썬의 리스트는 함수 밖에서 선언되어, 함수 내부에서 변경되어도 함수 밖에서 변경이 적용되기 때문에 print(sum(visited)-1) 이 정답이 될 수 있다.

3. 코드

import sys

input = sys.stdin.readline

computer = int(input())

network = int(input())

graph = [[] for _ in range (computer+1)]

visited = [0] * (computer+1)

for _ in range (network):

a, b = map(int, input().split())

graph[a].append(b)

graph[b].append(a)

def dfs(v):

visited[v] = 1

for node in graph[v]:

if visited[node] == 0:

dfs(node)

dfs(1)

print(sum(visited)-1)

4. 느낀점

이번에는 DFS를 이용하여 풀이해 보았다.

DFS와 BFS 두 가지 방법을 모두 이용하여 그래프 탐색 연습을 할 수 있는 좋은 문제였던 것 같다.

DFS는 재귀, BFS는 deque를 활용한 큐를 이용한다는 것이 핵심이었다.

더 다양한 문제를 풀어보면서 익숙해져야 할 것 같다.

오늘 하루도 쌓였다.