[Baekjoon] 2606_바이러스

Silver III

문제(출처: https://www.acmicpc.net/problem/2606)

---

<바이러스>

문제 

 

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

 

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

출력 

 

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

 

문제 풀이

- my solution

import sys

def bfs(graph, start): #너비 우선 탐색
    visited=[]
    temp=[start]

    while temp:
        a=temp.pop(0)
        if a not in visited: # 아직 방문하지 않았다면
            visited.append(a)
            temp+=graph.get(a)
    return visited

if __name__=='__main__':
    num=int(input())
    pair=int(input())

    graph={}
    for i in range(num): #init
        graph[i+1]=[]

    for i in range(pair): # graph 연결
        a,b=map(int ,sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    print(len(bfs(graph,1))-1) # 1번 컴퓨터는 제외

 

• bfs
  - visited list 선언, temp list에 시작할 컴퓨터 번호 넣어서 선언
  - temp list가 빌 때까지 반복: temp에서 맨 앞 값을 뽑아와 아직 방문한 컴퓨터가 아니라면 visited에 추가하고 temp list에 그 컴퓨터와 연결된 컴퓨터 번호를 추가
• main
  - 컴퓨터 수, 간선 수 입력
  - 정점과 연결된 정점을 dict로 표현 -> key 값들 선언
  - 양방향 간선 이므로 양쪽 key에 value 추가
  - 출력: bfs의 반환 값의 길이 - 1(1번 컴퓨터 제외)

---

생각🤔

 

이 문제는 bfs로 풀거나 dfs로 풀어 해결할 수 있는 문제이다. 어제 bfs와 dfs 개념 문제를 해결하고 나니 쉽게 해결할 수 있었다.

근데... 맞게 풀고 있는건가? 

 

---