(cpp) Baekjoon 1260번 문제 ‘DFS와 BFS’ - 그래프탐색,DFS,BFS

on Programming Languages

Baekjoon 1260번 문제 ‘DFS와 BFS’ - 그래프탐색,DFS,BFS

문제

풀이

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, v, f,t; //점갯수,간선수,시작점,from지점,to지점
bool check_dfs[1001];
bool check_bfs[1001];
queue<int> q;
vector<int> g[1001]; //graph,각 점이 어디와 연결되는지 알려줌.!!크기 할당하기
//g[1] = [2,3,4]
//g[2] = [1,4]
//g[3] = [1,4]
//g[4] = [1,2,3]

//깊이 우선탐색. 현재 위치에서 갈 수 있는 곳 중 숫자 작은 곳으로 일단 간다.
void dfs(int v) {	
	check_dfs[v] = true; //v정점 지나면 true;
	cout << v << " "; 
	//현재 정점에서 갈 수 있는 곳 하나씩 탐색
	for (int i = 0; i < g[v].size(); i++) {
		int next = g[v][i];
		if (!check_dfs[next]) {
			dfs(next);
		}
	}
}

//넓이 우선탐색. 현재 위치에서 가능한 모든 곳을 큐에 넣음
void bfs(int v) {
	q.push(v); //다녀온 정점을 기록할 큐.다녀오고 나면 비워준다. que가 모두 빌때까지 반복
	check_bfs[v] = true; //v점 지났으니까 true;

	//q가 비어있지 않는 동안 반복(=q가 빌 때까지 반복)
	while (!q.empty()) {
		int cur = q.front(); //현재 정점은 q의 맨앞요소(최솟값 먼저 탐색)
		q.pop(); //현재 위치만 기억하고 q는 비워줌
		cout << cur << " ";

		for (int i = 0; i < g[cur].size(); i++) {
			int next = g[cur][i]; //현재그래프에 포함된 모든 점이 다음 지점으로 가능

			//근데 그 다음 지점이 간 적 없는(false)곳이여야함.
			if (!check_bfs[next]) {
				check_bfs[next] = true;
				q.push(next); //next로 가능한 점 담겨있지만 최솟값 지점 먼저 감.
			}

			//간 적 있는 곳이면 더이상 push할게 없어서 결국엔 q가 비게 됨.
			//그럼 모든 곳을 탐색한 셈이 돼서 끝남.
		}
	}
}

int main(void) {
	cin >> n >> m >> v;
	int ret = m;
	while (ret--) {
		cin >> f >> t;
		//양방향그래프
		g[f].push_back(t);
		g[t].push_back(f);
	}

	for (int i = 1; i <= n; i++) {
		sort(g[i].begin(), g[i].end()); //작은 곳먼저 가니까 오름차순 정렬
	}

	dfs(v);
	cout << "\n";

	bfs(v);
	
	return 0;
}