Baekjoon 2606번 바이러스

문제

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

걸린 시간

00 : 37 : 40

풀이

Python3

def dfs_mat(g, v, visited):
    visited[v] = True
    for w in range(0, g.n):
        if g.adj_mat[v][w] and not visited[w]:
            dfs_mat(g, w, visited)

class matrixGraph():
    def __init__(self, max_vertices):
        self.n = 0 # vertex count
        self.max_vertices = max_vertices
        self.adj_mat = [[0 for _ in range(0, max_vertices)] for _ in range(0, max_vertices)]

    def insert_vertex(self):
        if self.n+1 > self.max_vertices:
            print("graph is full")
        else:
            self.n += 1

    def insert_edge(self, start, end):
        # vertex count - 1 = index
        if start > self.n-1 or end > self.n-1:
            print("out of area")
        else:
            self.adj_mat[start][end] = 1
            self.adj_mat[end][start] = 1

if __name__ == "__main__":
    vertex = int(input())
    edge = int(input())    

    g = matrixGraph(vertex)

    for _ in range(0, vertex):
        g.insert_vertex()

    for _ in range(0, edge):
        u, v = map(int, input().split())    
        g.insert_edge(u-1, v-1)    

    visited = [False for _ in range(0, vertex)]

    dfs_mat(g, 0, visited)

    count = 0
    for i in visited:
        if i == True:
            count += 1

    # 1번 노드를 제외한 감염된 컴퓨터 수 
    print(count-1)

인접 행렬로 구현한 그래프를 깊이 탐색을 통해 1번 컴퓨터와 연결된 모든 컴퓨터를 체크표시하여 감염된 컴퓨터 수를 계산하였다.

인접 행렬의 인덱스는 0번부터 사용하므로 컴퓨터(정점) 번호의 시작이 1부터인 문제 입력에서 1을 빼준 후 사용한다.