[C++] 백준 - #2066 : 바이러스

문제 설명

입력

출력

풀이과정

오랜만에 풀어보는 BFS 문제였다.

다른 BFS문제들과는 다르게 노드들간의 연결 여부만 확인하면 되기 때문에
입력으로 주어지는 board[][]의 해당 인덱스에서의 값을 1로 바꾸어주었다.

시작은 1번 컴퓨터부터 이므로, BFS에서 사용하는 queue에는 1을 먼저 넣어준다.

그리고 1번 컴퓨터는 바이러스 감염상태이므로, vis[1]또한 1로 바꿔준다.

그 후 방문했는지의 여부(이 문제에서는 바이러스에 걸렸는지의 여부)를 의미하는 vis[i] = 0이고, board[i][j] = 1인 i에 대해서만 vis[i]를 1로 바꿔주고(방문했음을 의미), queue에 push해준다.

위 과정을 board의 모든 칸에 대해 실행하면 정답을 얻을 수 있다. 그리고 얻은 정답에 1을 빼주어야 한다. 문제에서 정답을 1번 컴퓨터를 제외한 나머지 컴퓨터에 대해 묻고 있기 때문이다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int board[101][101];
bool vis[101];
int n, m;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int a, b;
	int cnt = 0;

	queue <int> q;
	q.push(1);
	vis[1] = 1;

	cin >> n;	
	cin >> m;

	for (int i = 0; i < m; i++)
	{
			cin >> a >> b;
			board[a][b] = 1;
			board[b][a] = 1;
	}


	while (!q.empty())
	{
		int cur = q.front(); q.pop();

		cnt++;

		for (int i = 1; i <= n; i++)
		{
			if (board[cur][i] == 1 && vis[i] == 0)
			{
				vis[i] = 1;
				q.push(i);
			}
		}
	}

	cout << cnt - 1;
	
}

피드백

BFS를 오랜만에 풀어보니 역시 어려웠다.

BFS 구현을 너무 수학 공식 외우듯이? 하는 것이 아니라 문제 조건에 알맞게 구현하는 것이 참 중요한 것 같다.

그리고 대부분의 BFS/DFS 문제가 그렇듯이 둘 중 하나만 써야 하는 경우는 거의 없다. DFS를 찾아봤는데 재귀 함수 형태로 많이 구현하는 듯 했다. 아직은 BFS가 편하긴 하다.