BFS(Breadth-First Search), DFS(Depth-First Search) 관련 실수 및 풀이
2019. 9. 2. 14:30ㆍProgramming/C++
1. 개념
* DFS(깊이우선탐색) : 현재 정정에서 갈수있는 점들까지 들어가면서 탐색
* BFS(너비우선탐색) : 현재 정점에 연결된 가까운 점들부터 탐색
2. 구현 방법
* DFS(깊이우선탐색) : 스택 혹은 재귀함수로 구현
* BFS(너비우선탐색) : 큐를 이용하여 구현
3. 기본적인 bfs, dfs의 구현
#bfs_dfs.cpp
#include
#include
using *namespace* std;
*bool* LINKED[10][10];
*bool* VISITED[100];
*int* N, M; *//N = 정점의 개수 , M = 간선의 개수*
*void* dfs (*int* *n*) {
*//recursive, visit*
VISITED[n] = true;
cout << n << " ";
for (*int* i = 0; i < N; i++) {
if (LINKED[n][i] && !VISITED[i]) {
dfs(i);
}
}
}
*void* bfs(*int* *n*) {
*//queue에 visit->push, visit all -> pop*
queue<*int*> Q;
VISITED[n] = true;
Q.push(n);
while (!Q.empty()) {
*int* tmp = Q.front();
Q.pop();
cout << tmp << " ";
for (*int* i = 0; i < N; i++) {
*// 배열을 쓴 이유가, 링크드가 아니니까.. 그래서 하나하나 다 봐야하기때문이다.*
if (LINKED[tmp][i] && !VISITED[i]) {
VISITED[i] = true;
Q.push(i);
}
}
}
}
*int* main() {
*// cin >> N >> M;*
*// for (int i = 0; i < M; i++) {*
*// int from, to;*
*// cin >> from >> to;*
*// LINKED[from][to] = true;*
*// LINKED[to][from] = true;*
*// }*
*//memset(VISITED, false, sizeof(VISITED));*
*//cout << endl;*
bfs(0);
N = 5;
LINKED[0][1]=true;
LINKED[1][0]=true;
LINKED[0][2]=true;
LINKED[2][0]=true;
LINKED[1][3]=true;
LINKED[3][1]=true;
LINKED[1][4]=true;
LINKED[4][1]=true;
LINKED[3][4]=true;
LINKED[4][3]=true;
LINKED[2][4]=true;
LINKED[4][2]=true;
bfs(0);
return 0;
}
4. BFS: 최단거리 검색(Graph 구현, level[거리] 체킹)
- 핵심: 모든 그래프의 성분을 검사하되, 모든 길을 가지는 않는다.(너비탐색)
# bfs_level.cpp
#include
#include
using *namespace* std;
*bool* LINKED[7][7];
*bool* VISITED[7][7];
*int* D[7][7];
*int* dx[4] = { 0,+1,0,-1 }; *//12시부터 시계방향*
*int* dy[4] = { -1,0,+1,0 }; *//12시부터 시계방향*
*void* bfs(*int* *x*, *int* *y*) {
*//queue에 visit->push, visit all -> pop*
queue<pair<*int*, *int*>> Q;
VISITED[x][y] = true;
Q.push(make_pair(x, y));
*//x, y값 현재 + 방향 따지기 => 백업*
while (!Q.empty()) {
pair<*int*, *int*> tmp = Q.front();
Q.pop();
*//현재 큐의 front에 있는 x, y 초기화*
*int* x = tmp.first;
*int* y = tmp.second;
cout << x << " " << y << endl;
*//12시부터 시계방향*
for (*int* i = 0; i < 4; i++) {
*int* nx = x + dx[i]; *//check x 좌표 인자*
*int* ny = y + dy[i]; *//check y 좌표 인자*
*//경로 밖인 경우에는 push 안해!*
if (0 <= nx && nx <= 4 && 0 <= ny && ny <= 4) {
*//방문 안했고, linked 되어있으면*
if (LINKED[nx][ny] && !VISITED[nx][ny]) {
if(!VISITED[nx][ny]){
VISITED[nx][ny] = true;
D[nx][ny] = D[x][y]+1; *//🔥🔥방문하지 않은 곳을 들르면서 새로 한칸씩 이동하니까!!*
Q.push(make_pair(nx, ny));
*//[실수]잘 들어갔는지 확인 -> 여기서 Q.front 확인하면 지금 넣은거확인이 아니라 이전에 넣은걸 확인하는게 되는거라.. 잘못체킹함*
*//cout << nx << ", ny" << ny;*
*//cout << "insert " << Q.front().first << "," << Q.front().second << " " << endl;*
}
}
}
}
}
}
*int* main() {
for (*int* i = 0; i < 5; i++) {
for (*int* j = 0; j < 5; j++) {
*//scanf("%1d", &LINKED[i][j]);*
LINKED[i][j] = true;
D[i][j]= 0;
}
}
bfs(0, 0);
*//cout D(distance)*
for (*int* i = 0; i < 5; i++) {
for (*int* j = 0; j < 5; j++) {
*//scanf("%1d", &LINKED[i][j]);*
*//cout << VISITED[i][j] << " ";*
cout << D[i][j] << " ";
}
cout << endl;
}
return 0;
}**위 코드에서 배운 점**
- D[nx][ny] = D[x][y]+1; //🔥🔥🔥기존에 있는것을 활용 하는 방식이 개인적으로 약한 것 같다.이부분 잘볼것!!
- 이와같이 모든 길이 able의 경우에, 각 D(distance)[][]성분이 현재 위치( [x][y] )에 1을 더한값이다.
**헷갈렸던 부분**
- 이부분에서, tmp = 3일때 LINKED[3][4] 성분이 존재하는데도 불구하고 검사하지 않는데,(VISITED[4]) ~~얘는실제로일차원배열의 성분을 검사하는거여서그렇기도한데~~ 당연히 하지 않는것이다.
- ⇒ 왜냐? bfs는 최단거리를 찾는거라 연결되어있는애들을 다 가면, 길은 가지 않으니ㅏ!!!
- 그래서,
만약에 길의 값들이 달라서 확인해야하거나, 길을 모두 가야한다면 추가로 설정을 해주어야한다.
- 굳~이 비유를 해보면, 길보다는 땅에!! 집중해야한다는것이다. (level)
BFS의 길탐색 문제의 프로세스는
1. 유효한 값인가?(==범위안에 있는 값인가? == 갈수 있는 길인가?)
2. 방문 했는가?
3. if(미로문제) { 땅이 갈수있는 곳인가(1) 아닌가 (0);}}
를 확인해야한다는 것!!
BFS관련 흔히 하는 실수
처음 BFS, DFS를 접하고 했던 실수인데 많은 친구들도 헷갈려하는 부분이라 기재해본다.
Q. for 문 이중으로 i, j (0,0)~(n-1,n-1)까지 봐야하나?!
A. 놉. 아니용. 배열의 경우와 Queue를 생성하여 pair로 push해놓고, pop해가며 경로를 찾는 경우를 헷갈리고계시군요!!
// int N = 7; 요고요고 노필요.
이 의문의 핵심은, Queue를 제대로 이해하는데에 있다.
지금 단순한 bfs 루틴 구현시 for문을 이중으로 하나하나 모두 직접 bfs를 돌려야하는것이 아니냐?를 고민하고 있다면,
Queue의 pop, push를 다시한번 하나하나 넣어보며 생각해보는 것을 추천한다!
차이점을 봅시다.
bool LINKED[10][10];
bool VISITED[100];
int N, M; //N = 정점의 개수 , M = 간선의 개수
void bfs(int n) {
//queue에 visit->push, visit all -> pop
queue Q;
VISITED[n] = true;
Q.push(n);
while (!Q.empty()) {
int tmp = Q.front();
Q.pop();
cout << tmp << “ “;
for (int I = 0; I < N; I++) {
// 배열을 쓴 이유가, Q.push에 pair로 연결된게 아니니까.. 그래서 하나하나 다 봐야하기때문이다.
if (LINKED[tmp][I] && !VISITED[I]) {
VISITED[I] = true;
Q.push(i);
}
}
}
}연결된게 아니라서, 직접 이차원배열을 만들어 연결된것을 찾는게 아니라 모든 경우를 다 지나가면서,
VISIT[]를 확인하는게 핵심이었음
하지만 지금은 좌우가 연결되어있는지를 모두 확인하며, Q에 push 하고,
-> push된 성분이 또 while문을 돌면서 확인해서
-> VISITED를 확인만 하면 되므로 for문으로 하나하나 거치지 않아도 모든 성분을 거친다.
결국, bfs(0) 의 시작으로 연결되어있는, 모든 길을 거치고나서야 bfs는 pop을 시작하기 때문에!
위의 질문의 답은 NO! 이다.
예제로 풀어보자
/* Copyright (c) 2019, Pongsoyun
Global Media Of Soongsil Univ.
This file is licenced under a Creative Commons license:
https://github.com/pongsoyun
*/
//No. 2178
#include <iostream>
#include <queue>
using namespace std;
bool VISITED[100][100];
int N, M; //N = 정점의 개수 , M = 간선의 개수
int LINKED[100][100];
int D[100][100];
int dx[4] = { 0,+1,0,-1 }; //12시부터 시계방향
int dy[4] = { -1,0,+1,0 }; //12시부터 시계방향
void bfs(int x, int y) {
//queue에 visit->push, visit all -> pop
queue<pair<int, int>> Q; //좌표 저장가능한 Q 생성
VISITED[x][y] = true;
Q.push(make_pair(x, y));
while (!Q.empty()) {
pair<int, int> tmp = Q.front();
Q.pop();
//현재 큐의 front에 있는 x, y 초기화
int x = tmp.first;
int y = tmp.second;
// cout << x << " " << y << endl;
//12시부터 시계방향
for (int i = 0; i < 4; i++) {
int nx = x + dx[i]; //check x 좌표 인자
int ny = y + dy[i]; //check y 좌표 인자
//경로 밖인 경우에는 push 안해!
if (0 <= nx && nx <= N-1 && 0 <= ny && ny <= M-1) {
//방문 안했고, linked 되어있으면
if (LINKED[nx][ny] && !VISITED[nx][ny]) {
if(!VISITED[nx][ny]){
VISITED[nx][ny] = true;
D[nx][ny] = D[x][y]+1; //🔥🔥방문하지 않은 곳을 들르면서 새로 한칸씩 이동하니까!!
Q.push(make_pair(nx, ny));
}
}
}
}
}
}
int main() {
cin >> N >> M;
for(int i =0 ;i<N; i++){
for(int j=0;j<M;j++){
scanf("%1d", &LINKED[i][j]);
D[i][j]= 0;
}
}
bfs(0,0);
//Distance Map
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < M; j++) {
// cout << D[i][j] << " ";
// }
// cout << endl;
// }
//first location -> +1
cout << D[N-1][M-1]+1<<endl;
return 0;
}접근법
D[][] (distance) 를 계산하는 이차원 배열을 하나 생성해 BFS를 이용했다.
백준 2667 단지번호 붙이기
/* Copyright (c) 2019, Pongsoyun
Global Media Of Soongsil Univ.
This file is licenced under a Creative Commons license:
https://github.com/pongsoyun
*/
//No. 2667
#include "stdio.h"
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
bool VISITED[25][25];
int N; //INPUT, N*N
int LINKED[25][25];
int D[25][25]; //distance
int dx[4] = { 0,+1,0,-1 }; //12시부터 시계방향
int dy[4] = { -1,0,+1,0 }; //12시부터 시계방향
//int cNum; //몇개씩 붙어있나 확인, 갈수없는 길을 만나면 0으로 초기화
int cnt; // 몇개의 단지가 있는지 확인(마지막에 -1)
vector<int> vec; //땅떵어리
void bfs(int x, int y) {
//queue에 visit->push, visit all -> pop
queue<pair<int, int>> Q; //좌표 저장가능한 Q 생성
VISITED[x][y] =true;
D[x][y]=cnt;
Q.push(make_pair(x, y));
while (!Q.empty()) {
pair<int, int> tmp = Q.front();
int x = tmp.first;
int y = tmp.second;
Q.pop();
//현재 큐의 front에 있는 x, y 초기화
//길이 끊기면
// if(D[x][y]==0){
// cNum = 0 ;
// }
//12시부터 시계방향
for (int i = 0; i < 4; i++) {
int nx = x + dx[i]; //check x 좌표 인자
int ny = y + dy[i]; //check y 좌표 인자
//경로 밖인 경우에는 push 안해!
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
//방문 안했고, linked 되어있으면
if (LINKED[nx][ny] && !VISITED[nx][ny]) {
if(!VISITED[nx][ny]){
VISITED[nx][ny] =true;
//cNum +=1;
D[nx][ny] = cnt; //🔥🔥방문하지 않은 곳을 들르면서 새로 한칸씩 이동하니까!!
//1이 몇개, 2가 몇개 ...
Q.push(make_pair(nx, ny));
}
}
}
}
}
}
int main() {
cin >> N;
//cNum = -1;
cnt = 0;
//지도 입력
for(int i =0 ;i<N; i++){
for(int j=0;j<N;j++){
scanf("%1d", &LINKED[i][j]);
D[i][j]= 0;
VISITED[i][j]=false;
}
}
//단지 표시 + 가용길
for(int i =0 ; i<N; i++){
for(int j = 0 ;j<N;j++){
if(VISITED[i][j]==false && LINKED[i][j]==1){
cnt +=1;
bfs(i,j);
}
}
}
// cout << "-------------------------" << endl ;
// for(int i =0 ; i<N; i++){
// for(int j = 0 ;j<N;j++){
// cout << D[i][j];
// }
// cout << endl;
// }
int checkN = 0;
cout << cnt;
vector<int> CHECK;
//1,2...cnt 개수 뽑음
for(int cntN = 1; cntN<=cnt; cntN++){
for(int i =0 ; i<N; i++){
for(int j = 0; j<N; j++){
if(D[i][j] == cntN){
// 성분의 개수 파악해서 프린트
checkN +=1;
}
}
}
CHECK.push_back(checkN);
checkN = 0;
}
sort(CHECK.begin(), CHECK.end());
for(int i=0 ; i<(int)CHECK.size(); i++){
cout << endl<<CHECK[i];
}
return 0;
}접근법
bfs를 for문을 이용해 길이 끊겼을 때를 해결해야겠다
→ bfs를 최소한으로 사용 할 수 있도록 연결된 길인지 체크하면서 가야겠다
→ 변수 계산을 어디서 해야할지ㄹ가 중요하다.
배운 점
뭔가가 잘 나오지 않을 떄, 계속 출력해나가면서 나오지 않는 경우의 규칙을 찾는다.
'Programming > C++' 카테고리의 다른 글
| GC(Garbage Collection), Native Code vs Managed Code (0) | 2019.09.09 |
|---|---|
| [알고리즘] sort with STL, c++ 람다함수 (0) | 2019.08.31 |