[Baekjoon][Python] 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 알고리즘을 사용하는 것이었는데, 개념을 한 번 학습해두면 여러모로 잘 사용할 수 있어 좋은 것 같다. 파이썬으로 그래프를 구현하는 것이 익숙치 않아 코드 정리가 깔끔하진 않지만, 앞으로의 코드에서는 조금 더 깔끔한 코드를 작성할 수 있을 것 같다.
Author And Source
이 문제에 관하여([Baekjoon][Python] 2606번 바이러스), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ktaewon98/BaekjoonPython-2606번-바이러스저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)