Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 컴퓨터공학 #자료구조 #스택 #c++ #알고리즘 #백준문제풀이
- 잔
- BOJ #컴퓨터공학 #C++ #알고리즘 #자료구조
- 컴퓨터공학 #Java #자바 #클래스 #객체 #인스턴스
- HTML #CSS
- 컴퓨터공학 #c #c언어 #문자열입력
Archives
- Today
- Total
영벨롭 개발 일지
[백준 BOJ][C++]2606번 바이러스 풀이: BFS/DFS 본문
https://www.acmicpc.net/problem/2606
첫 번째 입력은 그래프의 노드 수, 두 번째 입력은 그래프의 엣지 수를 의미합니다.
그 다음 입력으로 엣지 수 만큼의 연결된 두 노드가 주어집니다.
처음 문제를 접했을 때, 엣지 정보를 저장하는 2차원 배열을 선언하고 이를 바탕으로 인접리스트로 전체 그래프를 만들었으나 틀렸습니다 ㅠㅠ 아마 시간이 너무 걸린듯 합니다.
때문에 두 노드 u, v 입력이 주어지면 그래프 g[u][v]와 g[v][u]를 1로 설정하는 작업을 해주었습니다. 이는 두 노드 u, v가 연결되었음을 의미합니다.
이제 BFS나 DFS로 문제를 해결하면 됩니다!
저는 BFS를 이용하였습니다.
Queue의 front 노드를 pop하여 그 노드와 연결된 모든 노드를 검사하여 아직 방문하지 않았다면 queue에 push 하고 방문 표시를 합니다. 이 작업을 queue가 empty일 때까지 반복하면 깔끔하게 풀립니다:)
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
int n;
int e;
int visit[101] = { 0, };
int ans = 0;
int g[101][101];
void bfs() {
queue<int> open_list;
open_list.push(1);
visit[1] = 1;
while (!open_list.empty()) {
int temp = open_list.front();
open_list.pop();
ans++;
for (int i = 1; i <= n; i++) {
if (g[temp][i] == 1 && visit[i] == 0) {
visit[i] = 1;
open_list.push(i);
}
}
}
}
int main(void) {
int u, v;
cin >> n >> e;
for (int i = 1; i <= e; i++) {
cin >> u >> v;
g[u][v] = g[v][u] = 1;
}
bfs();
cout << ans - 1;
return 0;
}
반응형
'알고리즘 문제 풀이 > BOJ' 카테고리의 다른 글
[백준 BOJ][C++]10026번 적록색약 풀이: BFS/DFS (0) | 2022.02.27 |
---|---|
[백준 BOJ][C++]1012번 유기농 배추: BFS/DFS (0) | 2022.02.26 |
[백준 BOJ][C++]2667번 단지번호붙이기: BFS/DFS (0) | 2022.02.26 |
[백준 BOJ][C++]2193번 이친수 풀이: DP (0) | 2022.02.25 |
[백준 BOJ][C++]15990번 1, 2, 3 더하기 5: DP (0) | 2022.02.25 |