[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가 편하긴 하다.
Author And Source
이 문제에 관하여([C++] 백준 - #2066 : 바이러스), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@josuncom/C-백준-2066-바이러스저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)