Baekjoon 1260번 DFS와 BFS

문제

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

걸린 시간

-

풀이

C++

#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>
#define MAX 1001
using namespace std;

int N, M, V;
int adj_mat[MAX][MAX] = {0};

void dfs(){
    int visited[MAX] = {0};
    visited[V] = 1;
    stack<int> s;
    s.push(V);
    printf("%d ", V);
    int v; // vertex

    while(s.size() != 0){
        v = s.top();
        s.pop();

        if(!visited[v]){
            visited[v] = 1;
            printf("%d ", v);    
        }

        // 작은 값이 먼저 pop 되도록 거꾸로 push
        for(int w = N; w >= 1; w--){
            if(adj_mat[v][w] && !visited[w]){
                s.push(w);
            }
        }
    }
    printf("\n");
}

void bfs(){
    int visited[MAX] = {0};
    visited[V] = 1;
    queue<int> q;
    q.push(V);
    printf("%d ", V);
    int v; // vertex

    while(q.size() != 0){
        v = q.front();
        q.pop();

        if(!visited[v]){
            visited[v] = 1;
            printf("%d ", v);
        }

        for(int w = 1; w < N+1; w++){
            if(adj_mat[v][w] && !visited[w]){
                q.push(w);
            }
        }
    }
    printf("\n");
}

int main(){
    scanf("%d %d %d", &N, &M, &V);

    int T = M;
    int s, e;
    while((T--) != 0){
        scanf("%d %d", &s, &e);
        adj_mat[s][e] = 1;
        adj_mat[e][s] = 1;
    }

    dfs();
    bfs();

    return 0;
}

정점의 번호가 1부터 시작하는 문제의 조건의 맞추어 인접행렬의 최대 크기를 1만큼 높이고 0행 0열은 사용하지 않았다. 입력받은 간선 정보에서 1씩 빼주어 사용해도 되는데 그냥 문제 조건대로 구현해보고 싶었다.

c++ 문법도 익히고 bfs, dfs 도 복습할 겸 풀어본 문제.

오랜만에 쓰는 c++ 적응하기 어려웠다.