Baekjoon Training #2606

---

#2606 바이러스

---

직관적으로 푼 풀이

import sys
input=sys.stdin.readline

num=int(input())    # 컴퓨터의 수 입력
net=int(input())    # 연결된 컴퓨터쌍의 수
pc=[0 for _ in range(num+1)]    # 컴퓨터수+1개의 0으로 이루어진 pc리스트 생성
pc[1]=1     # 감염시킬 1번 컴퓨터를 1로 세팅

for i in range(net):
    a,b=map(int,input().split())
    if (pc[a]==1 or pc[b]==1):  # 연결된 컴퓨터중 한대라도 감염되어있다면
        # 전부 감염됨
        pc[a]=1
        pc[b]=1
# 1번 컴퓨터로 인해 감염된 컴퓨터의 수 출력
print(pc.count(1)-1)

첫번째 풀이는 문제를 읽자마자 간단한 방법이 생각나서 바로 코드작성을 해서 풀어보았다.
예시 입력에 대한 답은 제대로 나오는 것으로 확인이 되었는데 어떤 이유에서 인지 백준에서는 시간초과도 아니고 '오답'이 나왔다.

추후에 생각해보니 연결관계가 순서대로 제시 되지 않는 경우 문제가 생겨서 이중 for문을 돌려야할 것 같다. 하지만 시간초과가 예상된다.

스터디에서 코드를 공유하고 문제점을 찾아보고자 하고 원래 BFS로 풀기 위해 찾은 DFS,BFS 알고리즘 문제이니 BFS로 풀이를 해보았다.

---

BFS풀이

import sys
input=sys.stdin.readline

num=int(input())    # 컴퓨터의 수 입력
net_num=int(input())    # 연결된 컴퓨터쌍의 수
net = [[] for i in range(num + 1)] # 연결 상태 저장할 list
check = [] # 탐색할 컴퓨터 배열
pc = [0] * (num + 1) # 탐색한 컴퓨터 방문 확인용 배열

for i in range(net_num):
	a, b = map(int, input().split())
	net[a].append(b)    # a에는 b와 연결되었음을 저장
	net[b].append(a)    # b에는 a와 연결되었음을 저장

check.append(1) # 가장 먼저 탐색할 1번 컴퓨터 check에 삽입

while check: # check 리스트 전체 조사
    tmp = check.pop(0) # 탐색할 컴퓨터 pop해서 tmp에 담아둠
    pc[tmp] = 1 # 탐색완료
    for i in net[tmp]: # 연결된 컴퓨터 전수조사
        if pc[i] != 1: # 탐색하지 않은 경우 탐색 진행
            pc[i] = 1 # 탐색완료
            check.append(i) # check 리스트에 삽입
           #print(check)
#print(net)
#print(pc)
print(pc.count(1)-1) # 1번 컴퓨터가 감염시킨 컴퓨터 수 출력

BFS알고리즘을 이용하여 반복적으로 탐색을 진행하여 전수조사를 끝마치는 방식이다. 이해를 돕기위해 주석처리 해놓은 print(check), print(net), print(pc)를 통해 예시 입력에서 각 리스트에 담기는 내용들을 함께 첨부한다.

#입력
7
6
1 2
2 3
1 5
5 2
5 6
4 7

#출력 (중간과정 포함)
[2]
[2, 5]
[5, 3]
[3, 6]
[[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
[0, 1, 1, 1, 0, 1, 1, 0]
4

check리스트에 연결된 pc들이 반복적으로 일시적으로 입력되어 코드가 실행되는 것을 볼 수 있다.

---