백준 2606 : 바이러스 문제풀이, 파이썬

백준 2606번 : 바이러스 문제풀이 [파이썬] 

---

<문제>

 

2606번 문제의 내용은 아래와 같습니다. 

 

바이러스

 

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 복사

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1 복사

4

---

 

 

<작성한 코드>

1) DFS로 풀기

2)BFS로 풀기

---

 

 

<코드 풀이>

본 문제는 그래프 알고리즘의 DFS와 BFS를 모두 적용하여 풀어보았다.

뭐랄까 DFS는 재귀함수만 쓰면 되니까 BFS보다 사용하기 익숙하고 편해서(?)

가장 먼저 풀이방법으로 생각하게 되는거같다,,,,

 

 

1) DFS로 풀기

문제를 풀기위한 초기 설정은 DFS나 BFS 모두 위와 동일하다

입력값들을 받기위한 변수를 만들고,

그래프를 표현하고, 방문처리를 해주기 위한 리스트와

최종적으로 바이러스에 걸리게되는 컴퓨터의 수를 출력해야하기 때문에

이를 세기 위한 cnt 변수도 만들었다. 

 

 

과정을 좀 살펴보자면,,,

(숫자 1은 방문O, 숫자 0은 방문X)

 

1) 가장 먼저 시작 컴퓨터 1을 방문처리 해준다. (1번 컴퓨터는 카운트X)

2) 반복문을 통해 그래프 안에서 1번 컴퓨터와 연결된 컴퓨터들을 다 확인한다.

3) 이때 그 컴퓨터가 아직 방문하지 않은 컴퓨터라면, 카운트+1한다.

4) 그 컴퓨터에 다시 dfs를 돌린다. 

5)마지막으로 카운트 cnt를 리턴한다.

 

여기까지가 DFS 풀이방법이다. 

 

---

 

2)BFS로 풀기

여기서부터는 BFS로 푸는 풀이방법이다.

초기 세팅부분은 위의 DFS와 차이가 없다. 

 

BFS 부분을 살펴보자면 위와 같다.

사실 특별한건 없고, 항상 풀었던 bfs 풀이방식 그대로다. 

1) 큐에 가장 먼저 시작노드(컴퓨터) 1넣고

2) 그래프에서 1번이랑 연결되어 있는 친구들을 확인하고

3) 아직 방문처리 되지 않은 것들이라면 방문처리를 하고, 큐에 집어넣고 카운트 +1

 

위에 dfs에서는 cnt값을 return하고 가장 마지막에 print로 출력했는데

여기는 bfs 정의할때부터 마지막에 출력하도록 작성했다.

별다른 이유는 없다,,, 그냥 작성하다보니 얘는 이렇게 했네