문제의 난이도 : Silver 2
문제의 난이도는 Silver에서 상위 티어지만,
BFS 알고리즘을 알고 있다면 전혀 어렵지 않다.
이 문제는 상당히 BFS의 정석 같은 문제라고 할 수 있다.
문제를 풀 때 중요한 키는
'컴퓨터 간 연결 관계를 어떻게 표현할 것인가?'
라고 할 수 있다.
다양한 방법이 있을 수 있는데,
이런 방법들이 있을 수 있다.
다만, 1번과 2번의 경우 first나 key만 검사하는 것이 아니라 second나 value도 검사해야 한다.
물론 3번도 마찬가지지만 실제로 문제를 풀 때 코드가 더 직관적이다.
그래서 개인적으로는 3번 방법을 이용하여 문제를 풀게 되었다.
(그러나, 메모리 공간에 민감한 문제라면 1번과 2번을 고려했을 것이다.)
#include <iostream>
#include <queue>
using namespace std;
// 인접행렬로 표현한 컴퓨터 간 연결 관계
int computerMap[101][101];
// BFS 알고리즘에서 방문했는지 확인하는 배열
bool visited[101];
// 바이러스에 걸리게 되는 컴퓨터의 수
int cnt;
int N, M;
void bfs() {
queue<int> q;
// Starting point는 1번 컴퓨터
q.push(1);
// -1로 설정한 이유는
// 1번에서 탐색하면 ++하여 0으로 만들고
// 그 다음 걸린 것부터 1이 되기 때문.
cnt = -1;
while(!q.empty()) {
int key = q.front();
q.pop();
cnt++;
for(int i=1; i<= N; i++) {
if(computerMap[key][i] == 1 && visited[i] == false) {
visited[i] = true;
q.push(i);
}
}
visited[key] = true;
}
}
int main() {
cin >> N >> M;
for(int i=0; i<M; i++) {
int x, y;
cin >> x >> y;
// 쌍방에 연결관계가 있다는 것을 표현
computerMap[x][y] = 1;
computerMap[y][x] = 1;
}
bfs();
cout << cnt;
return 0;
}
[백준][알고리즘][C++] 16165 걸그룹 마스터 준석이 (1) | 2020.03.18 |
---|---|
[백준][C++]17269 이름궁합 테스트 (0) | 2020.02.22 |
댓글 영역