[4w] DFS, BFS

DFS, BFS

DFS, BFS란?
DFS 문제 : 백준 1260번
코드

#include<bits/stdc++.h>
using namespace std;

int N, M, V;
vector<int> graph[1001];
vector<int> result;
bool visited[1001];

void dfs(int num) {
	result.push_back(num);
	visited[num] = true;
	for (int i = 0; i < graph[num].size(); i++) {
		int next = graph[num][i];
		if (!visited[next]) dfs(next);
	}
}

void bfs(int num) {
	queue<int> iQ;
	iQ.push(num);
	result.push_back(num);
	while (!iQ.empty()) {
		int now = iQ.front();
		iQ.pop();
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			if (!visited[next]) {
				iQ.push(next);
				visited[next] = true;
				result.push_back(next);
			}
		}
	}
}

int main() {
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a); //양방향
	}
	for (int i = 1; i <= N; i++) // 각 정점의 인접 리스트를 정렬
		sort(graph[i].begin(), graph[i].end());
	fill(visited, &visited[1001], false); //dfs초기화
	dfs(V);
	for (int i = 0; i < result.size(); i++) cout << result[i] << " ";
	cout << "\n"; 
	result.clear();
	fill(visited, &visited[1001], false); visited[V] = true;  //bfs 초기화
	bfs(V);
	for (int i = 0; i < result.size(); i++) cout << result[i] << " ";
	return 0;
}

BFS 문제 : 백준 13549번

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int N, K;
bool visited[100001] = {false};

int bfs() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, N});
    while (!pq.empty()) {
        pair<int, int> now = pq.top();
        pq.pop();
        int nowSec = now.first;
        int nowPoint = now.second;

        if (nowPoint < 0 || nowPoint > 100000) continue;  // 범위를 벗어나는 경우 무시
        if (visited[nowPoint]) continue;  // 이미 방문한 경우 무시

        visited[nowPoint] = true;

        if (nowPoint == K) return nowSec;

        pq.push({nowSec + 1, nowPoint + 1});
        pq.push({nowSec + 1, nowPoint - 1});
        pq.push({nowSec, nowPoint * 2});
    }
    return -1;  // 이 경우는 발생하지 않음
}

int main() {
    cin >> N >> K;
    cout << bfs();
    return 0;
}

DFS, 그리고 Backtracking

Backtracking이란?
문제 : 백준 9663번

코드

#include <iostream>
#include <vector>
using namespace std;
int N, result=0;
int board[15];
int abs(int num) {
    if(num<0) return (num*(-1));
    else return num;
}
bool promise(int depth){
    int nowNum=board[depth];
    for(int i=0;i<depth;i++){
        if(nowNum==board[i]||(depth-i)==abs(nowNum-board[i])) return false;  //열||대각 검증
    }
    return true;
}

void dfs(int depth){

    for(int i=1;i<=N;i++){
        board[depth]=i;
        if(promise(depth)){
            if(depth==(N-1)){
                result++;
                return;
            }
            dfs(depth+1);
        }
    }
}

int main(){
    cin>>N;
    dfs(0);
    cout<<result;
    return 0;
}