2606 - 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

- 그래프 탐색 (BFS 사용)

 

import sys
input = sys.stdin.readline

from collections import deque

class Graph:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0] * size for _ in range(size)]
        self.visited = [0] * size

    def addEdge(self, v1, v2):
        self.matrix[v1][v2] = self.matrix[v2][v1] = 1

    def bfs(self, start):
        q = deque([start])
        self.visited[start] = 1

        while len(q) != 0:
            k = q.pop()
            for i in range(self.size):
                if self.matrix[k][i] == 1 and self.visited[i] == 0:
                    q.appendleft(i)
                    self.visited[i] = 1
            
        
        print(sum(self.visited) - 1)
    
g = Graph(int(input()))
for _ in range(int(input())):
    n1, n2 = map(int, input().split())
    g.addEdge(n1-1, n2-1)

g.bfs(0)

웅오오아아아아아

첫 번째로 PS 풀 때 그래프랑 탐색 써봤음!!!

 

문제는 완전 간단하게 그래프 구현하고, 탐색 돌려서 방문한 정점 개수 구하는 문제인데

구현해보고 풀어본건 처음이라 재밌었다

 

 

혼자 그래프 공부하고 탐색 인터넷으로 찾아봤으면 어려울 것 같은데

디미고에서 배운게 도움이 엄청 됐다 히히