[백준] 2606번 - 바이러스 (python)

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

---

풀이과정

 

뻘짓

n = int(input())
t = int(input())

l = [1] + [0] * (n - 1)
c = []
for x in range(t):
	c.append(input())

for s in c:
	x, y = map(int, s.split())
	if l[x - 1] == 1 or l[y - 1] == 1:
		l[y - 1] = 1
		l[x - 1] = 1

for s in reversed(c):
	x, y = map(int, s.split())
	if l[x - 1] == 1 or l[y - 1] == 1:
		l[y - 1] = 1
		l[x - 1] = 1

print(l.count(1) - 1)

그냥 인자를 받고 배열 형식으로 양방향으로 돌리면서 감염을 시키면 쉽게 가능할 줄 알았었는데 실패!

생각지 못했던 예외 케이스들이 더 있는 거 같음

 

그래서 고민을 하다가 DFS나 BFS 형식처럼 재귀를 돌려서 모든 케이스를 판단해야 할 거 같아서
BFS 형식으로 짜는 것으로 바꿨었습니다.

 

기본적인 코드 전개 방법은 1부터 감염이 시작이 된다고 하였으니
1부터 BFS가 돌아가면서 1이랑 연결되어있는 값들이 있다면 그 값들도

모두 BFS가 돌아가는 방식으로 코드를 작성하였습니다.

 

생겼던 문제들

파이썬에서의 2차원 배열 생성 방법

# X 잘못된 방법
com = [[0] * (X)] * (Y)

# O 옳은 방법
com = [[0 for i in range(X)] for j in range(Y)]

 

com = [[0] * (X)] * (Y)

ex)

com = [[0] * (5)] * (5)
com[0][0] = 1
print(com)

>> 
[[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]

파이썬에서 2차원 배열을 생성해서 사용하려고 하였더니 위와 같은 방식으로 선언을 하고

com[0][0] = 1 로 바꾸니 com[n][0]의 모든 값들이 1로 바꿔지는 것을 확인할 수 있었다.

그래서 해당 내용을 해결해보고자 검색을 하니

파이썬 2차원 배열 선언, 이 방법은 피하세요!

위와 같은 내용을 확인할 수 있었다. 

위와 같은 방식으로 2차원 배열을 생성하면 얕은 복사라는 것이 진행이 되어서

1개의 인자만 바꿔도 전체가 바뀐다는 내용이 었었고 2차원 배열을 생성하고 싶으면 

com = [[0 for i in range(X)] for j in range(Y)]

ex)
com = [[0 for i in range(5)] for j in range(5)]
com[0][0] = 1
print(com)

>> 
[[1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

위와 같은 형식으로 배열을 생성해야 한다는 내용을 확인할 수 있었습니다.

 

code

n = int(input())
t = int(input())

com = [[0 for i in range(n + 1)] for j in range(n + 1)] 
check = [0] * (n + 1)
num = 0

for _ in range(t):
	x, y = map(int, input().split())
	com[x][y] = 1
	com[y][x] = 1

def dfs(c):
	check[c] = 1
	for x in range(n + 1):
		if com[c][x] == 1 and check[x] == 0:
			dfs(x)

dfs(1)

print(check.count(1) - 1)

후기쓰

오랜만에 알고리즘을 푸니 확실히 어렵고 어떻게 접근을 해야 할지 머릿속에서 안 돌아가더라고요.

이제는 자주자주 풀어가며 굳어버린 뇌를 좀 깨워야겠네요.