DFS와 BFS | Notion

🍋 문제링크

https://www.acmicpc.net/problem/1260

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 3656 KB

시간 : 4 ms

🍉 Code

#include <iostream>
#include <queue>
#include <algorithm>

int N;
int M;
int V;
std::vector <int> arr[1001];
std::queue <int> bfs_arr[1001];
std::queue <int> dfs_arr[1001];
std::queue <int> bfs_result;
int visited[1001] = {0 , };

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void my_queue_sort(int i)
{
    sort(arr[i].begin(), arr[i].end());
    for(int j = 0 ; j<arr[i].size() ; j++){
        dfs_arr[i].push(arr[i][j]);
        bfs_arr[i].push(arr[i][j]);
    }
}

void input()
{
    int x;
    int y;
    std::cin >> N >> M >> V;
    while (M--){
        std::cin >> x >> y;
        arr[x].push_back(y);
        arr[y].push_back(x);
    }

    // queue 정렬
    for(int i = 1 ; i<=N ; i++)
        my_queue_sort(i);
}

void dfs(int V)
{
    std::cout << V << " ";
    
    visited[V] = 1;

    int num = dfs_arr[V].size();
    for(int i = 0; i < num ; i++){
		int next = dfs_arr[V].front();
		if(visited[next] == 0){
			dfs(next);
		}
        dfs_arr[V].pop();
	}
}

void bfs(int V)
{
    // visited 초기화
    for (int i = 0; i < N + 1; i++) visited[i] = 0;

    bfs_result.push(V);
    visited[V] = 1;

    while(!bfs_result.empty()){
		int tmp = bfs_result.front();
		bfs_result.pop();
		std::cout << tmp << " ";

        while(!bfs_arr[tmp].empty()){
			if(visited[bfs_arr[tmp].front()] == 0){
				bfs_result.push(bfs_arr[tmp].front());
				visited[bfs_arr[tmp].front()] = 1;
			}
            bfs_arr[tmp].pop();
		}
	}
}

void print_val()
{
  dfs(V);
  std::cout << std::endl;
  bfs(V);
}

int main()
{   
	input_faster();
	input();
	print_val();
	return (0);

🥝 메모

그래프를 탐색하는 방법에는 크게 **깊이 우선 탐색(DFS)**과 **너비 우선 탐색(BFS)**이 있습니다.

여기서 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,

그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다.

1. 입력값 저장

우선, DFS, BFS 를 구현하기 위해서는 입력값을 queue 에 저장하는 단계가 필요합니다.

만약 아래의 경우로 입력값이 들어온다면