[코딩테스트 C++] DFS와 BFS

오늘의 문제

DFS와 BFS

나의 풀이

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

using namespace std;
// DFS와 BFS

bool check[1001] = {false, };
vector<int> dfs(vector<vector<int>> n, int start){
    vector<int> answer;
    answer.push_back(start);
    check[start] = true;
    for(int i=0;i<n[start].size();i++){
        if(check[n[start][i]] == false){
            vector<int> r = dfs(n, n[start][i]);
            answer.insert(answer.end(), r.begin(), r.end());
        }
    }
    return answer;
}
vector<int> bfs(vector<vector<int>> n, int start){
    vector<int> answer;
    queue<int> q;
    q.push(start);
    check[start] = true;
    while(!q.empty()){
        int p = q.front();
        answer.push_back(p);
        q.pop();
        for(int i=0;i<n[p].size();i++){
            if(check[n[p][i]] == false){
                q.push(n[p][i]);
                check[n[p][i]] = true;
            }
        }
    }
    return answer;
}

풀이 법

• dfs는 재귀로, bfs는 queue로 풀었다.

모범 답안

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define MAX_SIZE 1000+1

using namespace std;

vector<bool> isVisited;
vector<uint16_t> vs;
vector<vector<uint16_t>> graph;
queue<int> q;

void dfs(int vertex)
{
	if (isVisited[vertex] == 1)
	{
		return;
	}
	cout << vertex << " ";
	isVisited[vertex] = true;

	for (uint16_t i = 0; i < graph[vertex].size(); i++)
	{
		dfs(graph[vertex][i]);
	}
}
void bfs(int vertex)
{
	isVisited[vertex] = true;
	q.push(vertex);

	while (!q.empty())
	{
		int value = q.front();
		q.pop();
		cout << value << " ";
		for (uint16_t i = 0; i < graph[value].size(); i++)
		{
			if (!isVisited[graph[value][i]])
			{
				q.push(graph[value][i]);
				isVisited[graph[value][i]] = true;
			}
		}
	}
}

배울 점

• Xcode가 algorithm을 include하지도 않았는데 오류를 안뱉어서 컴파일 오류난지도 모르고 계속 시도했었다 ㅋㅋ