[백준/Python] 2606 : 바이러스

 

 

 

dfs 깊이 우선 탐색으로 풀 수 있었던 문제이다.

저번에 썼던 코드 그대로 사용하면 될 줄 알았는데 결과는 제대로 출력이 되지만 막상 백준에 제출했을 때에는 런타임에러가 계속 발생해서 예외처리를 한 뒤에야 통과되었음

 

런타임 에러 이유는 NZEC 에러라고 해서 try except 문으로 예외 처리를 해주었는데, 솔직히 이걸 안했을때 왜 통과가 안되는 지에 대한 정확한 이유는 잘 모르겠다..

 

import sys
input = sys.stdin.read

class Node:
    def __init__(self, value):
        self.data = value

class Graph:
    def __init__(self):
        self.graph = {}
        self.visit = []
    
    def create(self, v, data): # 인접리스트 graph[v]에 data추가
        node = Node(data)
        if v not in self.graph:
            self.graph[v] = []
        self.graph[v].append(node)

    def dfs(self, v):
        self.visit.append(v)
        for node in sorted(self.graph.get(v, []), key=lambda x: x.data): # graph[v]는 정점 v 의 인접 리스트
            if node.data not in self.visit:
                self.dfs(node.data)

g = Graph()

try:
    nodes = input().splitlines()
    if len(nodes) == 0:
        raise ValueError("Input is empty")

    num = nodes.pop(0) # 컴퓨터의 수
    com = nodes.pop(0) # 연결되어 있는 컴퓨터 쌍의 수 (연결 수)

    for node in nodes:
        a, b = map(int, node.split())
        g.create(a, b)
        g.create(b, a)

    g.visit = []  # 방문 리스트 초기화
    g.dfs(1)  # 깊이 우선 탐색
    print(len(g.visit) - 1)

except Exception as e:
    print("An error occurred:", e)
    sys.exit(1)

 

저번과 동일하게 node들을 한 번에 sys.stdin.read로 입력받고 splitlines로 분리하여 리스트 생성

 

첫 번째와 두 번째 줄의 입력은 각각 컴퓨터의 수와 연결 수를 의미하므로 pop()과 동시에 num, com에 저장

이렇게 하면 이제 splitline을 한 nodes 리스트의 첫 번째 원소부터 노드 정보가 들어가있게 된다.

 

그 후로는 nodes 리스트에 있는 노드들을 하나씩 create로 생성해주고, dfs 탐색을 한 뒤에 결과물인 visit 리스트에서 시작 노드를 뺀 나머지 원소의 수를 출력하게 하면 문제에서 요구하는 바이러스에 걸리는 컴퓨터 수이다.