백준 2606번/DFS

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와

네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

 

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자.

1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다.

하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

 

문제 예시

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.

이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

입력 예시

 

출력 예시

 

풀이

먼저 예시 그림에서 보는 것처럼 각 컴퓨터를 노드로서 갖는 그래프 구조를 정의해야했다.

처음에는 2차원 배열을 통해 인접 행렬을 만들어야 하는 게 아닌가 싶었지만

다행히도 파이썬에서는 dictionary 자료구조를 통해서 그래프 구조를 손쉽게 나타낼 수 있다.

 

*그래프 표현 예시*

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

 

또한 1번 컴퓨터에서 출발하여 연결된 모든 노드들을 탐색하고 탐색한 노드 수(1번 노드는 제외)를 반환하면

그게 답이라는 사실을 알고 따라서 그래프 탐색 알고리즘인 DFS와 BFS 2가지의 선택지가 있었다.

이번 문제에서는 DFS를 사용하여 풀어보았다.

 

import sys


def dfs(graph, start_node):  # DFS 탐색 알고리즘.
    visited = list()  # 탐색한 노드 (큐)
    need_visit = list()  # 탐색해야할 노드 (스택)
    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop()
        if node not in visited:  # 이미 간곳이 아니면 탐색하고 연결된 모든 노드들을 스택에 넣는다.
            visited.append(node)
            need_visit.extend(graph[node])

    return len(visited)-1


graph = dict()
vertex_num = int(sys.stdin.readline())

for i in range(1, vertex_num+1):  # 입력받은 컴퓨터 수 만큼 vertex 생성.
    graph[i] = list()

edge_num = int(sys.stdin.readline())

for i in range(edge_num):  # 입력받은 edge 수 만큼 연결 관계를 표현
    key, value = map(int, sys.stdin.readline().split())
    graph[key].append(value)
    graph[value].append(key)

print(dfs(graph, 1))

아래 부분의 입력받는 부분을 먼저 보시면 처음 입력받은 컴퓨터 수만큼 vertex를 생성해주고

그다음 입력받은 edge 수만큼 key, value 형식을 통해 연결 관계를 딕셔너리로서 정의하였다.

 

이어서 dfs 함수를 통해 DFS 탐색을 진행하는데 방문해야 할 노드는 스택으로 관리하고 방문한 노드는 큐(편의상 list로서 구현)를 사용하여 관리하였다. 중요한 점은 깊이 우선 탐색을 하기 위해서는 현재 노드와 연결된 모든 노드를 스택에 넣는 행위를 반복하고 가장 마지막에 넣은 노드를 먼저 꺼내어 탐색하는 방식으로 진행해야 한다.