[Algorithm] 백준 2606 - 바이러스 in Python(파이썬)

💡 백준 2606:

BFS 탐색

🌱 코드 in Python

알고리즘: BFS

import sys

input = sys.stdin.readline
n = int(input())
t = int(input())
c = [[] for i in range(n + 1)] # 각 컴퓨터마다 연결 된 컴퓨터 정보 저장
q = [] # 탐색할 컴퓨터 배열
visit = [0] * (n + 1) # 탐색한 컴퓨터 방문 확인용 배열

for i in range(t):
	c1, c2 = map(int, input().split())
	c[c1].append(c2) # c[1] = = [2, 5] c[2] = 3 ... 과 같이 저장
	c[c2].append(c1)

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

while q: # 탐색할 컴퓨터가 있는 동안
    tmp = q.pop(0) # 팀색할 컴퓨터 pop
    visit[tmp] = 1 # 방문 처리
    for i in c[tmp]: # 해당 컴퓨터에 연결된 컴퓨터 모두 조사
        if visit[i] != 1: # 아직 방문하지 않은 컴퓨터라면
            visit[i] = 1 # 방문처리 후
            q.append(i) # q에 삽입

print(visit[2:].count(1)) # 1번 컴퓨터 제외 2번 컴퓨터부터 방문한 컴퓨터 개수 반환

이번주는 BFS, DFS와 관련된 문제를 풀어볼 예정이다
관련 문제들이 대부분 BFS로도 풀 수 있고, DFS로도 풀 수 있다보니
번갈아서 풀어보고, 가능하면 두 방법을 다 이용해서 풀어보려 한다

이번 문제는 BFS를 활용하여 풀었다
컴퓨터가 네트워크 상에 양방향으로 연결되어있기 때문에

각 컴퓨터마다 자신에서 연결된 컴퓨터를 자신의 배열에 삽입하고,
연결된 컴퓨터의 배열에 자신을 삽입하여 양쪽 모두에게서 결과를 얻을 수 있도록 해야 한다

나는 처음에 연결을 단방향으로 이해해서 C2->C1에 해당하는 배열 삽입을 안했다가 실패했었다 또륵

위 예제의 경우
c = [[], [2, 5], [1, 3], [2], [7], [2, 6], [5], [4]] 와 같은 형태로 입력이 저장된다

이후 로직을 살펴보면
q = [1] -> q = [] -> q = [2, 5] && visit = [0, 1, 1, 0, 0, 1, 0, 0] 이 첫번째 while 반복문의 결과이다
따라서 1에서 직접 연결되어있는 가장 첫 단계 컴퓨터인 2, 5번 컴퓨터를 먼저 탐색하게 된다

그 다음 반복문에서는 q = [2, 5] -> q = [5, 3] -> q = [3, 6] && visit = [0, 1, 1, 1, 0, 1, 1, 0] 이 되어
다음 단계인 3, 6번 컴퓨터에 대한 탐색이 이루어진다

이에 따라 너비 우선 탐색이 가능하게 되는 것이다

🧠 기억하자

1. BFS, DFS...
   - 42seoul 라피신때도 꽤나 고전했고,, 아직 고전하고 있는,, 알고리즘이라..
   험난한 1주일이 될 것만 같다 ㅠㅠ
   - 하우에버! 이번에야말로 기필코 완전히 내껄로 만든다!!
   

백준 2606 바로가기