백준 2606 : 바이러스 _ C++

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

2606번: 바이러스

#그래프 #BFS알고리즘 #silver3

 

회고

 

문제 자체는 쉬워서 바로 BFS 알고리즘을 적용해서 풀었다.

computer 배열을 통해 연결 된 컴퓨터를 저장 해 주었는데, 잘 풀다가 마지막에 엉뚱하게 주석처리를 하는 바람에 '틀렸습니다' 가 떴다. 

for (int i = 0; i < e; i++) {
		cin >> x >> y;
		computer[x][y] = 1;
		//computer[y][x] = 1;
	}

[y][x]를 주석처리 하는 바람에 어떤분이 올려주신 반례가 통과되지 않았고 해당 반례를 통과하지 못한것을 보고 주석처리에 문제가 있었음을 깨닫게 되었다. (그냥 처음 짠 대로 제출했으면 바로 통과했을것을..ㅋ)

2
1
2 1 #1

 

아무튼 여러 그래프 문제를 풀어봤더니 이제 조금은 bfs에 익숙해져가는 것이 느껴진다. 

 

코드

#include <iostream>
#include <queue>
#define MAX 101
using namespace std;

int computer[MAX][MAX];
int visit[MAX];
int n, e;
queue<int> q;

int main() {
	cin >> n;
	int x, y;
	int cnt = 0;
	cin >> e;
	for (int i = 0; i < e; i++) {
		cin >> x >> y;
		computer[x][y] = 1;
		computer[y][x] = 1;
	}
	q.push(1);
	visit[1] = 1;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 1; i <= n; i++) {
			if ((computer[x][i] == 1 || computer[i][x] == 1) && visit[i] != 1) {
				q.push(i);
				cnt++;
				visit[i] = 1;
			}
		}
	}
	cout << cnt;
	return 0;
}