[BOJ] 백준 1260 dfs와 bfs 간단한설명과 코드 C++

27 Mar 2020

Reading time ~2 minutes

문제 정보

백준 ( BOJ ) 1260 dfs와 bfs

문제 풀이 : dfs, bfs

문제 출처 : https://www.acmicpc.net/problem/1260

bfs vs dfs 구현 편의성?

우선은, 제가 bfs와 dfs 다룰때 구현하는 방식으로는

bfs 는 큐를,

dfs는 재귀를 사용하는 편입니다.

dfs도 스택으로 해도 되지만.. 뭔가 그게 편하더라구요

(어차피, 함수 재귀도 스택이니까 결국은 똑같은..)

어찌됬든 둘다 유명한 거니까, 간단하게 제가 하는방식을

보기 쉽게 수도코드로만 짚고 넘어가도록 하겠습니다.

bfs

bfs(start){
  큐 에 시작점 넣기
  시작점 방문 체크 
  while(큐 남아있을떄까찌){
   스타트 = 큐 프론트
   큐 팝
    for(int i =0 ; i < n ; i++){
      if ( 방문안했던지점 ? &  갈수 있는지점 ) 
        큐에 i 넣기
      }
  }
}

굳이 한글로 했어야 할까 싶은 수도코드가 되었네요.;;;

dfs

 dfs(start){
  for(int i =0 ; i < n; i++){
    if( 방문안했던지점 ? & 갈수 있는 지점 ) 
      dfs(i)

구현하는데 걸리는 시간은 뭐 dfs 가 더 짧습니다.

그러나 dfs를 써야만 하는 경우라면, 무언가 더줄줄이 달려있을떄가 더 많죠..

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> graph;
vector<int> dfsVisited;
vector<int> bfsVisited;
int countOfPoint;
int startPoint; 
int lines; 

void dfs(int point) {
	dfsVisited[point] = 1;
	cout << point+1 << " ";
	for (int i = 0; i < countOfPoint; i++) {
		if (dfsVisited[i] == 1)
			continue;
		if (graph[point][i] == 1)
			dfs(i);
	}
}
void bfs(int point) {
	queue <int> remain;
	remain.push(point);
	cout << point+1 ;
	bfsVisited[point] = 1;
	while (!remain.empty()) {
		point = remain.front();
		remain.pop();
		for (int i = 0; i < countOfPoint; i++) {
			if (bfsVisited[i] == 1)
				continue;
			if (graph[point][i] == 1) {
				bfsVisited[i] = 1;
				remain.push(i);
				cout << " " << i+1 ;
			}
		}
	}
}


int main() {
	int start, end;

	cin >> countOfPoint >> lines >> startPoint;

	graph.assign(countOfPoint, vector<int>(countOfPoint, 0));
	bfsVisited.assign(countOfPoint, 0);
	dfsVisited.assign(countOfPoint, 0);
	for (int i = 0; i < lines; i++) {
		cin >> start >> end;
		start--;
		end--;
		graph[start][end] = 1;
		graph[end][start] = 1;
	}
	dfs(startPoint-1);
	cout << endl;
	bfs(startPoint-1);
}

백준 C++dfs bfs