[2606] 바이러스

• 입력: 컴퓨터 개수 N(100 이하의 자연수), 컴퓨터 연결된 쌍 M, M개의 쌍이 주어진다.(양방향)
• 출력: 1번 컴퓨터와 연결된 컴퓨터 개수
• 알고리즘: Floyd-Warshall
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; int main() { int n, m, u, v; scanf("%d %d", &n, &m); vector<vector<bool> > computer(n + 1, vector<bool>(n + 1, false)); for(int i=0; i<m; i++){ scanf("%d %d", &u, &v); computer[u][v] = computer[v][u] = true; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { if (i == k) continue; for (int j = 1; j <= n; j++) { computer[i][j] = computer[i][j] | (computer[i][k] & computer[k][j]); } } } int cnt = 0; for (int i = 2; i <= n; i++) if (computer[1][i]) cnt++; printf("%d\n", cnt); return 0; }

이 문제는 1번 컴퓨터와 연결된 컴퓨터만은 찾으면 되므로 DFS나 BFS를 이용해도 된다. 그리고 이것이 더 효율적이라고 생각한다.

나는 Floyd-Warshall이라는 알고리즘을 사용하였는데, 연결된 간선들을 이용하여 직접적인 간선을 추가하는 알고리즘이다. 이 알고리즘은 다대다 알고리즘이기 때문에 해당 문제는 일대다라 비효율적이라고 생각된다. 하지만 입력 개수가 작기 때문에 시간 문제가 생기지는 않았다.

• 문제 참고: https://www.acmicpc.net/problem/2606
• 알고리즘 참고 Floyd-Warshall