[python] 백준 2606번 바이러스

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번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

4

 

 

---

풀이

 

우선 내가 생각했던 방식은

입력받은 수를 단방향으로 배열에 저장시켜

2,5

3

7

2,6

 

앞에서부터 1번 컴퓨터라 가정했을때 연결되어있는 수를 저장시킨 후,

[2,5]가 있다면

2번 컴퓨터 값 [3]이 있으므로

또 3번 컴퓨터로 들어가서 값이 없으면 돌아오고,

2번 컴퓨터의 값 조회가 끝났으므로

5번 컴퓨터 값 [2,6]에서

2번 컴퓨터, 6번컴퓨터 값을 조회하는 식으로 생각했다

 

단, 이미 카운팅된 컴퓨터는 중복해서 세면 안되는데, 그 경우를 포함하여 전반적으로 어떤식으로 구현해야할지에 어려움이 있었다.

 

기본적으로 dfs의 개념은 알고 있었기 때문에 내가 설계한 알고리즘이 dfs 방법인것은 알았으나,

dfs를 어떻게 구현하는지 이번 문제를 해결하며 알게되었다.

 

우선 어려움의 주 문제였던 "이미 카운팅된 컴퓨터 중복 카운팅 X"는 visited 배열을 이용하여 구현할 수 있었다.

 

따라서 코드 설계를 아래와 같이 진행했다.

 

먼저 리스트는 양방향으로 아래와 같이 준비해두고, (인덱스는 헷갈리니까 1부터 사용 - 여기서 인덱스는 컴퓨터 번호)

🔽 [network] 

0	1	2	3	4	5	6	7
	2, 5	1, 3, 5	2	7	1, 2, 6	5	4

com = int(input())	#컴퓨터 수
lines = int(input())	#연결된 선의 개수
net = [[] for _ in range(com+1)]
for _ in range(lines):
    idx, num = map(int, input().split())
    
    net[idx].append(num)
    net[num].append(idx)

 

visited 배열도 모두 0으로 초기화 해준다. (방문하면 1로 설정)

🔽 [visited] 

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

visited = [0]*(com+1)

 

그리고 하나씩 순회하며 방문처리를 진행해준다

 

먼저 network[1] = [2,5] 이므로 카운팅을 진행하기에 앞서,

이전에 방문한적이 있는지 확인해야하므로

순서대로 visited[2]가 비었는지 체크해준후 비었으면

1

2, 5

> network

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

>visited

network[2]번을 아직 카운팅 안했다는것이다.

 

network[2]를 가서 visited 처리 해준후

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

>visited

 

해당 값인 [1,3,5]를 순서대로 카운팅 해준다.

2

1,3,5

>network

 

여기서 network[1] 은 이미 방문했으므로 (visited[1]==1이니까)

network[3]과 network[5]를 가준다.

 

마찬가지로 갈 때마다 visited처리를 해주고,

해당 인덱스의 값을 순회하며 가장 깊이 있는 노드를 방문하며 돌아오면 된다.

 

재귀를 이용하여 해당 부분을 구현할 수 있다.

def dfs(com_n):
    visited[com_n] = 1
    for i in net[com_n]:
        if visited[i]==0:
            dfs(i)

 

 

---

정답

import sys
input = sys.stdin.readline

com = int(input())
lines = int(input())

net = [[] for _ in range(com+1)]
visited = [0]*(com+1)

for _ in range(lines):
    idx, num = map(int, input().split())
    
    net[idx].append(num)
    net[num].append(idx)
    
    
def dfs(com_n):
    visited[com_n] = 1
    for i in net[com_n]:
        if visited[i]==0:
            dfs(i)
        

dfs(1)
print(sum(visited)-1)

 

bfs로 푸는 방법도 있겠지만 우선은 dfs부터 풀이해보았다