[백준/C++] 1260. DFS와 BFS

항상 로봇, 센서 프로그래밍만 하다가 오랜만에거의 3개월...? 알고리즘 학회가 개강해서 숙제로 문제를 풀어보았다.

벡터를 어떻게 선언했더라...?

라는 생각이 들자마자 ㅈ됨을 느끼고 학회 과제를 앞으로 제대로 내고 벌금도 안내는 일석이조 프로젝트를 시작하기로 다짐했다. 나름 학부에서 '농부(씨뿌리기...)'라고 불리는 교수님들만 골라서 자료구조, 알고리즘 수업을 수강했는데 다 까먹으면 과거의 나에게 미안하기 때문에 일단 ㄱ

너비우선 탐색과 깊이우선 탐색
BFS는 queue, DFS는 재귀함수로 구현한다.

BFS - 시작하는 노드에서부터 인접한 노드 중 방문하지 않은 노드를 모두 queue에 넣어주고 순서대로 Pop하면서 탐색
DFS - 시작하는 노드에서 방문하지 않은 노드 중 아무거나 잡아서(구현할 땐 그래프 입력 순서로 됨, 가끔 정점의 숫자 크기로 할 때도 있으니 그 때엔 호출 전에 싹다 정렬해줌) 쭉쭉 내려간다. 재귀함수이기 때문에 끝까지 내려가면 다시 그 전 스텝의 노드로 돌아가서 또 다른 가지로 탐색한다.

백준 1260. DFS와 BFS

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

bool visited[1001] = {false, };
vector <int> graph[1001];
queue <int> q;
int n, m, v;

void dfs(int x){
    visited[x] = true;
    cout<<x<<" ";
    for(int i = 0; i<graph[x].size(); i++){
        int y = graph[x][i];
        if(!visited[y]){
            dfs(y);
        }
    }
}

void bfs(int x){
    q.push(x);
    visited[x] = true;

    while(!q.empty()){
        int y = q.front();
        cout<<y<<" ";
        q.pop();

        for(int i = 0; i<graph[y].size(); i++){
            int next = graph[y][i];

            if(!visited[next]){
                q.push(next);
                visited[next] = true;
            }
        }
    }

}

int main(){
    cin>>n>>m>>v;
    int from, to;

    for(int i = 0; i<m; i++){
        cin>>from>>to;
        graph[from].push_back(to);
        graph[to].push_back(from);
    }
    
	//정렬 안하면 입력 순서대로 탐색함
    for(int i = 1; i<=n;i++){
        sort(graph[i].begin(), graph[i].end());
    }

    dfs(v);
    cout<<"\n";
    
    memset(visited, false, sizeof(visited));
    bfs(v);

    return 0;
}

문제에 따라서 정렬 안해도 되는 문제가 있는데 예제출력을 보니까 정점 번호 순서대로 탐색하는 문제라서 넣어줬다. 외않되... 하고 있었는데 작년에 푼 거 보니까 정렬이 빠졌더라...

그럼 내일도 퐈이팅