[CLASS 3]백준 2606번 - 바이러스

2606번 : 바이러스

 

DFS 혹은 BFS의 기초 문제이다. 둘 중 하나의 방법을 통해 1번 컴퓨터와 연결된 컴퓨터를 모두 방문한 후 그 수를 출력해주면 된다.

 

먼저 DFS와 재귀함수로 푼 풀이이다.

 

내 코드(DFS,재귀):

import sys
input = sys.stdin.readline

coms = [set() for _ in range(int(input())+1)]
for _ in range(int(input())):
    a, b = map(int,input().split())
    coms[a].add(b)
    coms[b].add(a)

def dfs(graph,v):
    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            dfs(graph,i)

visited = [False] * len(coms)
dfs(coms,1)
print(visited.count(True)-1)

 

가장 간단하고 알아보기 쉽다고 생각한다. 매 함수 호출마다 해당 번호의 컴퓨터와 인접한 컴퓨터에 방문했는지 확인하다가 방문하지 않은 컴퓨터가 있다면 방문처리 한 뒤, 재귀함수를 호출해주면 된다.

 

DFS지만 for문을 사용하여 풀 수도 있다.

 

내 코드(DFS,for):

import sys
input = sys.stdin.readline

coms = [[] for _ in range(int(input())+1)]
for _ in range(int(input())):
    a, b = map(int,input().split())
    coms[a].append(b)
    coms[b].append(a)

def dfs(graph,v):
    stack = [v]

    while stack:
        for i in graph[stack[-1]]:
            if not visited[i]:
                stack.append(i)
                visited[i] = True
                break
            if i == graph[stack[-1]][-1]:
                stack.pop()

visited = [False] * len(coms)
dfs(coms,1)
print(visited.count(True)-1)

 

dfs함수의 내부만 조금 바뀌었는데, 재귀함수는 스택으로 바꿀 수 있으므로 스택으로 바꾸어 구현한 것이다. 해당 컴퓨터의 인접 컴퓨터를 모두 확인했지만 방문하지 않은 컴퓨터가 없다면 스택에서 pop한 뒤 다른 최상위 컴퓨터에 대해 인접 컴퓨터를 확인하는 작업을 반복하면 된다. 스택이 비게 된다면 모든 컴퓨터를 방문한 것이다.

 

너비 우선 탐색으로도 해결할 수 있다.

 

내 코드(BFS):

import sys
from collections import deque
input = sys.stdin.readline

coms = [set() for _ in range(int(input())+1)]
for _ in range(int(input())):
    a, b = map(int,input().split())
    coms[a].add(b)
    coms[b].add(a)

def bfs(graph,root):
    queue = deque([root])

    while queue:
        n = queue.popleft()
        for i in graph[n]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

visited = [False] * len(coms)
bfs(coms,1)
print(visited.count(True)-1)

 

큐를 사용하기 위해 덱을 import하고 먼저 root를 덱에 집어넣은 뒤 popleft함수를 통해 앞에서 하나 빼고 해당 컴퓨터의 주변에 있는 컴퓨터를 모두 큐에 삽입한 뒤 다시 이를 반복한다. DFS에 비해 조금 더 직관적인 것 같다.