[BOJ] 2606. 바이러스
바이러스 성공출처분류
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 42013 | 18757 | 13072 | 43.358% |
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 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
풀이
알고리즘 분류가 플로이드 와샬로 되어있어서 플로이드 와샬에 대해 공부했다. 다익스트라 알고리즘이 한 정점에서 다른 정점으로 가는 최소 비용을 구하는 알고리즘이라면, 플로이드 와샬은 모든 정점 사이의 최소 비용 거리를 구할 수 있는 알고리즘이다.
'플로이드 와샬' 알고리즘의 기본 원리는 다른 정점을 거쳐서 목표 정점에 도착하는 비용과 곧바로 연결되는 비용을 비교하여 더 작은 비용을 찾아 계속해서 값을 갱신하는 것이다.
이 문제에서 비용을 구할 필요는 없기 때문에, 문제 풀이에 사용할 수 있는 원리는 중간 거점이 있을 때 도착 지점에 연결될 수 있는지만 확인하면 된다!
주의할 점은, 양방향 그래프이기 때문에 초기 설정과 값 갱신에 항상 이를 염두에 둬야 한다.
코드
import sys n = int(input()) #컴퓨터의 수 com = [i for i in range(1,n+1)] m = int(input()) #연결선 수 con = [[False]*(n+1) for _ in range(n+1)] for _ in range(m): i,j = map(int, sys.stdin.readline().rstrip().split()) con[i][j] = True con[j][i] = True for k in range(1,n+1): for i in range(1,n+1): for j in range(1,n+1): if con[i][j]==False and con[i][k]==True and con[k][j] == True: con[i][j] = True con[j][i] = True ans = con[1].count(True) ans = ans if ans==0 else ans-1 print(ans) | cs |
또한 BFS로 풀 수도 있다. 플로이드로 풀면 이차원 리스트를 사용하지만 BFS를 사용하기 위해 딕셔너리 자료구조로 연결리스트 형태를 만들어줬다.
코드
from collections import deque import sys n = int(input()) #컴퓨터의 수 com = [i for i in range(1,n+1)] m = int(input()) #연결선 수 con = {} q = deque() visited = [False]*101 visited[1] = True q.append(1) for _ in range(m): i,j = map(int, sys.stdin.readline().rstrip().split()) if i in con.keys(): con[i].extend([j]) else: con[i] = [j] if j in con.keys(): con[j].extend([i]) else: con[j] = [i] ans=0 while q: current = q.popleft() for c in con[current]: if visited[c] == False: visited[c] = True q.append(c) ans+=1 print(ans) | cs |
플로이드 vs BFS
플로이드는 3중 for문이 있어서 그런지 확실히 걸리는 시간이 길었다.
* 추가 * 파이썬 그래프 연결리스트 입력받기
내가 그래프 연결값 입력받는 방식이 너무 지저분하다고 생각은 했는데 다른 사람의 풀이에서 깔끔한 방법을 발견했다. 다음부터는 이렇게 써야겠다.
No comments: