[백준][python][그래프/BFS] 2606 바이러스 문제

2606번: 바이러스

 

✏️ 내가 작성한 코드 (BFS 사용)

# 조건 : 1번 컴퓨터가 바이러스에 걸림

def bfs(start):
    visit = 0 # 바이러스 걸린 컴퓨터를 셀 변수
    need_visit= [] # 큐 대신 리스트 사용
    need_visit.append(start) # 시작 컴퓨터 처음에 넣어줌

    while need_visit: # 리스트에 있는 값 모두 없어질때까지 while 돌아감
        node = need_visit.pop(0) # 큐 특성 이용 -> 맨 앞값 가져옴 *pop() : 맨뒷값 가져옴
        if not visited[node]:
            visited[node]=True
            if node != 1: # 1번 제외하고 횟수 세야함
                visit +=1
            for e in abj[node]: # 해당 컴퓨터에 연결된 컴퓨터들 돌아가면서 가져오고 리스트에 넣어줌
                if not visited[e]:
                    need_visit.append(e)

    return visit


start = 1 # 시작 컴퓨터 번호
computer = int(input()) # 컴퓨터의 수
connec = int(input()) # 연결되어 있는 컴퓨터 쌍의 수
abj = [[] for _ in range(computer+1)] # 연결된 컴퓨터 쌍 담을 리스트
visited = [False]*(computer+1)

for _ in range(connec):
    a,b = map(int,input().split()) # 한 쌍씩 연결되어 있는 컴퓨터 번호 주어짐
    abj[a].append(b) # 양방향이므로 각각 append해줌줌    abj[b].append(a)
    abj[b].append(a)

print(bfs(start))

 

✏️ 참고

'from collections import deque' 사용하여 큐를 이용하는 대신

리스트를 이용. pop(0) 써서 맨 앞값 가져옴