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언어
- Javascript
- 머신러닝
- BOJ
- PHP 웹페이지 만들기
- 백준
- 숙명여자대학교 정보보안 동아리
- 생활코딩
- 웹페이지 만들기
- c
- BOJ Python
- WarGame
- The Loard of BOF
- hackerrank
- 기계학습
- XSS Game
- CSS
- Sookmyung Information Security Study
- 파이썬
- Python
- lob
- c++
- 자료구조 복습
- hackctf
- 숙명여자대학교 정보보안동아리
- 드림핵
- 풀이
- HTML
- siss
- SWEA
Archives
- Today
- Total
혜랑's STORY
[BOJ_C++] 1260번 : DFS와 BFS 본문
code
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
int n, m, v;
int map[1001][1001];
bool flag[1001];
queue<int> q;
void dfs(int v) {
flag[v] = true;
cout << v << " ";
for (int i = 1; i <= n; i++) {
if (map[v][i] == 1 && flag[i] == false)
dfs(i);
}
}
void bfs(int v) {
q.push(v);
flag[v] = true;
cout << v << " ";
while (!q.empty()) {
v = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (map[v][i] == 1 && flag[i] == false) {
q.push(i);
flag[i] = true;
cout << i << " ";
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int x, y;
cin >> n >> m >> v;
for (int i = 0; i < m; i++) {
cin >> x >> y;
map[x][y] = map[y][x] = 1;
}
memset(flag, false, sizeof(flag));
dfs(v);
cout << "\n";
memset(flag, false, sizeof(flag));
bfs(v);
return 0;
}
- dfs는 깊이 우선 탐색으로 해당 노드에서 인접한 노드가 있다면 그 노드를 탐색하고 그렇지 않으면 옆 노드로 이동하여 탐색하게 된다.
- bfs는 너비 우선 탐색으로 해당 노드의 부모와 연결된 모든 노드를 탐색하고 더 이상 탐색할 노드가 없으면 해당 노드와 연결된 노드로 이동하며 탐색하게 된다.
결과
'무지성 공부방 > 알고리즘 해결' 카테고리의 다른 글
[BOJ_C++] 1012번 : 유기농 배추 (0) | 2021.08.17 |
---|---|
[BOJ_C++] 1697번 : 숨박꼭질 (0) | 2021.08.17 |
[BOJ_C++] 2811번 : 상범이의 우울 (0) | 2021.08.16 |
[BOJ_C++] 5671번 : 호텔 방 번호 (0) | 2021.08.16 |
[BOJ_C++] 14889번 : 스타트와 링크 (0) | 2021.08.16 |