백준2606 - 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

어제 UCPC 참여해서 고냥 광탈해버린 뒤 마음잡고 푼 문제다. 1번 컴퓨터에서 도달할 수 있는 모든 곳을 찾았다. 일 대 다 관계이므로 다익스트라 알고리즘을 수행하면 될 것 같았다. 1번 컴퓨터와 연결이 안 된 곳은 결과 값이 0으로 남아있어서 다음과 같이 풀었다.

 

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

vector<int> v[101]; //컴퓨터 100대가 연결되어 있는 정보
int d[101]; //다익스트라 결과를 담을 공간
int cnt; //1번에 연결되어 있는 컴퓨터의 수
int n, m; //n개의 컴퓨터, m개의 연결 정보

//다익스트라 알고리즘, 시작점을 넣어주면 종착점을 큐에 넣어주고 각각의 종착점에 연결되어 있는 곳을 탐색하며 나아간다. 탐색한 곳은 pop으로 제거
void dijkstra(int start) {
	queue<int> q; //비용이 모두 같은 다익스트라 알고리즘을 수행하기 때문에 일반 큐를 이용
	q.push(start);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < v[x].size(); i++) {
			if (!d[v[x][i]]) { //다익스트라 결과가 적용되지 않은 곳이면
				if (v[x][i] == 1) { //1번 노드는 무시
					continue;
				}
				d[v[x][i]] = d[x] + 1; //결과를 전에 도착한 곳 + 1로 갱신
				q.push(v[x][i]); //현재 도착점을 큐에 삽입
			}
		}
	}
}

int main() {
	//컴퓨터의 갯수와 정보의 갯수를 입력
	cin >> n;
	cin >> m;

	//연결되어 있는 정보를 큐에 삽입
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	//1번에서 다익스트라 수행
	dijkstra(1);

	//1번에 연결되어 있으면 0이 아닐테니 cnt를 늘려준다.
	for (int i = 1; i <= n; i++) {
		if (d[i]) {
			cnt++;
		}
	}

	cout << cnt;
}