[Baekjoon Online Judge] 백준 2606번 바이러스(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2606번 바이러스

(Python)

(글쓴날 : 2020.03.31)

 

---

* Baekjoon Online Judge, 백준 2606번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2606번 바이러스

---

1) 문제

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

2606번: 바이러스

---

2) 풀이 과정

일련의 순서쌍들이 주어지고 각 순서쌍들의 맞물린 숫자들이 서로 연결되어 있다고 가정했을 때, 1번과 연결된 숫자의 개수를 출력하는 문제입니다.

 

저의 경우, BFS를 적용해 문제에 접근했습니다.

먼저, 순서쌍들을 인접 리스트 형태의 그래프로 구현했는데, 이 문제의 경우 그래프의 방향이 중요합니다.

제가 푼 방식으로 이 문제에 접근할 경우, 만약 그래프가 유향(단방향) 그래프라면 탐색을 하지 못하는 정점이 생기게 됩니다.

따라서 무향(양방향) 그래프를 구현하였고, 그 후 너비 우선 탐색을 실시하여 1번과 연결된 숫자의 개수를 구해 문제를 해결하였습니다.

---

3) 코드

 

* Python 코드

from collections import deque
import sys
input = sys.stdin.readline
 
 
def BFS(dq):
    global visit, netWork
 
    while len(dq):
        virus = dq.popleft()
 
        if not visit[virus]:
            visit[virus] = True
 
            for netLine in netWork[virus]:
                if not visit[netLine]:
                    dq.append(netLine)
 
 
com = int(input())
visit = [False] * (com + 1)
 
netWorking = [tuple(map(int, input().split())) for _ in range(int(input()))]
netWork = [[0] for _ in range(com + 1)]
dq = deque()
 
for net in netWorking:
    netWork[net[0]].append(net[1])
    netWork[net[1]].append(net[0])
 
for netLine in netWork[1]:
    dq.append(netLine)
 
BFS(dq)
 
visit[0], visit[1] = False, False
 
print(visit.count(1))

---