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

8005 단어 baekjoonbaekjoon

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

좋은 웹페이지 즐겨찾기