[백준] 17086번: 바이러스 - Python

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

 

아이디어

• nodes리스트를 통해 카운트한 노드인지 아닌지 판단.
• bfs를 통해 연결된 노드들 탐색 -> deque() 사용
  • 간선을 모두 돌며 탐색하고자 한 값이 간선의 양 끝값중 같은게 있는지 판단
  • 같은게 있다면 그와 연결된 노드가 이미 탐색이 완료된 친구인지 판단
  • 탐색 전인 노드라면 q에 넣고 nodes 리스트에 탐색 표시 0->1
• 모두 완료 후 nodes리스트의 총 합 -1 출력 ( 1번 노드는 빼야함)

구현

import sys
from collections import deque

input = sys.stdin.readline

node_cnt = int(input())
line_cnt = int(input())

lines = [list(map(int, input().strip().split())) for _ in range(line_cnt)]

nodes = [0 for x in range(node_cnt+1)]
nodes[1] = 1

q = deque()
q.append(1)

while q:
    tmp = q.popleft()
    for line in lines:
        if line[0] == tmp and nodes[line[1]] == 0:
            q.append(line[1])
            nodes[line[1]] = 1
        elif line[1] == tmp and nodes[line[0]] == 0:
            q.append(line[0])
            nodes[line[0]] = 1

print(sum(nodes)-1)

마무리

간단 bfs 문제였다.

이런 문제를 풀 때에는 방문 체크용으로 만든 리스트를 또 어디에 재사용 할 수 있는지 생각하면 쉽다.