[BOJ-2606] 바이러스

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

2606번: 바이러스

---

[풀이]

전형적인 BFS 문제이다.

 

먼저 연결된 노드를 노드 관계 리스트로 나타냈다.

7 => 컴퓨터 개수(그래프 노드개수)

6 => 간선의 개수(그래프 연결관계)

1 2 => 노드1번과 노드2번 연결/ 노드2번과 노드1번 연결

2 3 => 노드2번과 노드3번 연결/ 노드3번과 노드2번 연결

1 5 => 노드1번과 노드5번 연결/ 노드5번과 노드1번 연결

5 2 => 노드5번과 노드2번 연결/ 노드2번과 노드5번 연결

5 6 => 노드5번과 노드6번 연결/ 노드6번과 노드5번 연결

4 7 => 노드4번과 노드7번 연결/ 노드7번과 노드4번 연결

 

연결된 노드 리스트

노드1: [2,5]

노드2: [1,3,5]

노드3: [2]

노드4: [7]

노드5: [1,2,6]

노드6: [5]

노드7: [4]

 

플로이드 와샬이 아닌 BFS로 풀었다.

1번컴퓨터가 바이러스에 걸렸으므로 먼저 큐에 (1)을 추가한다. 

큐에서 POP()을 할 때, now=1이다.

바이러스 시작점 컴퓨터는 카운트하지 않고,

1번 컴퓨터를 통해서 바이러스를 걸린 컴퓨터의 개수만 구한다.

 

즉 먼저 1번 컴퓨터와 연결된 컴퓨터(노드)를 구한다.

그 연결된 노드는 방문되지 않은 상태여야한다.

구했다면, 바이러스에 걸린 컴퓨터 리스트(get_virus)에 추가한다.

 

바이러스에 걸린 컴퓨터 리스트(get_virus)의 길이가 0보다 크면

그 길이값을 리턴한다.

get_virus 리스트의 길이가 0이라면 0을 리턴한다. 

---

[코드 (python)]

import sys
from collections import deque
q=deque()
N,E= 0,0
visited=None
connected=None

def bfs():
    global visited, connected
    get_virus=[] #1번노드 빼고걸림
    result=0
    
    while q:
        now=q.popleft()
        
        #현재노드가 아직 방문하지 않았다면
        if not visited[now-1]:
            visited[now-1]=True #now 번 컴퓨터 방문
        
            if now!=1: #1번이아닌 다른 컴퓨터가 바이러스에 걸렸다면-> 리스트에 추가한다.
                get_virus.append(now)

            # now와 연결된 노드리스트에서
            #아직 방문하지 않은 상태라면 큐에 추가
            for c in connected[now-1]:
                if not visited[c-1]:
                    q.append(c)
                    
    if len(get_virus)>0:
        result=len(get_virus)
    return result
    

def main():
    global N,E, visited, connected
    N= int(sys.stdin.readline()) #컴퓨터 수(노드수)
    E= int(sys.stdin.readline()) #간선의 개수
    visited=[False]*N #방문리스트
    connected= [ [] for _ in range(N)] #연결된 노드 리스트
    
    for _ in range(E):
        c1, c2= map(int, sys.stdin.readline().split())
        connected[c1-1].append(c2)
        connected[c2-1].append(c1)

    q.append(1) #1번컴퓨터가 웜바이러스에 걸렸다
    print(bfs())

if __name__=='__main__':
    main()