[Baekjoon][Python] 2606번 바이러스

2606번 바이러스

문제

풀이

이번 문제는 DFS를 이용하여, 해결하면 된다.
나는 직접 그래프라는 클래스를 만들어 그래프를 구현하였다.
파이썬으로는 딕셔너리와 리스트를 이용해 인접 리스트로 쉽게 구현가능했다.

문제를 잘 살펴보면, 그래프를 모두 만든 뒤에 1번 노드부터 DFS 탐색을 하면서 방문하지 않은 경우에 count를 증가시키면 된다. count가 감염된 컴퓨터 수이다. 최초에 1번 노드를 방문하기 때문에 출력을 할 땐 -1을 해주면 된다.

코드는 다음과 같다.

import sys

class Graph:
    def __init__(self):
        self.graph = {}
    def addVertex(self, vertex):
        self.graph[vertex] = []
    def addEdge(self, startVertex, endVertex):
        self.graph[startVertex].append(endVertex)

def searchInfection(graph, startVertex, visited, count):
    visited[startVertex] = 1
    count += 1
    for s in graph.graph[startVertex]:
        if visited[s] != 1:
            visited, count = searchInfection(graph, s, visited, count)
    return visited, count
            
# 컴퓨터의 수
N = int(sys.stdin.readline())

# 그래프 선언
cGrpah = Graph()
visited = []

# vertex 추가
for i in range(N):
    cGrpah.addVertex(i + 1)
    visited.append(0)
visited.append(0)

# 연결된 컴퓨터 쌍 수
M = int(sys.stdin.readline())

# edge 추가
for i in range(M):
    c1, c2 = map(int, sys.stdin.readline().split())
    cGrpah.addEdge(c1, c2)
    cGrpah.addEdge(c2, c1)
    
# 검색
count = 0
visited, count = searchInfection(cGrpah, 1, visited, count)


# 방문한 노드 개수
print(count - 1)

결론

이번 문제는 DFS 알고리즘을 사용하는 것이었는데, 개념을 한 번 학습해두면 여러모로 잘 사용할 수 있어 좋은 것 같다. 파이썬으로 그래프를 구현하는 것이 익숙치 않아 코드 정리가 깔끔하진 않지만, 앞으로의 코드에서는 조금 더 깔끔한 코드를 작성할 수 있을 것 같다.