백준 1260 - DFS와 BFS(C++)

문제 링크입니다 https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

문제 조건

출력 예시

BFS와 DFS를 모두 사용하는 문제였습니다.

방문할 수 있는 지점이 다수일 경우, 작은 수부터 출력하는 것을 주의해야 했습니다.

 

문제 접근 방법

1. 백터를 이용해 정점에서 갈 수 있는 다른 정점들을 저장합니다.

2. 시작 지점부터 DFS를 탐색하면서, 방문 노드를 출력합니다.

3. 시작 지점부터 BFS를 탐색하면서, 방문 노드를 출력합니다.

 

 

문제 접근 방법 - 2번

void dfs(int x) {
    check[x] = 1;
    cout << x << " ";
    for (int i = 0; i < line[x].size(); i++) {
        int xx = line[x][i];
        if (check[xx] == 0) {
            check[xx] = 1;
            dfs(xx);
        }
    }
}

재귀를 통해서 DFS를 구현했습니다

 

 

문제 접근 방법 - 3번

void bfs(int x) {
    check[x] = 1;
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int x1 = q.front();
        cout << x1 << " ";
        q.pop();
        for (int i = 0; i < line[x1].size(); i++) {
            int xx = line[x1][i];
            if (check[xx] == 0) {
                check[xx] = 1;
                q.push(xx);
            }
        }
    }
}

큐를 이용해서 BFS를 구현했습니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int N, M, start;
vector<int> line[1001];
int check[1001];

void dfs(int x) {
    check[x] = 1;
    cout << x << " ";
    for (int i = 0; i < line[x].size(); i++) {
        int xx = line[x][i];
        if (check[xx] == 0) {
            check[xx] = 1;
            dfs(xx);
        }
    }
}

void bfs(int x) {
    check[x] = 1;
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int x1 = q.front();
        cout << x1 << " ";
        q.pop();
        for (int i = 0; i < line[x1].size(); i++) {
            int xx = line[x1][i];
            if (check[xx] == 0) {
                check[xx] = 1;
                q.push(xx);
            }
        }
    }
}

void sort_line() {
    for (int i = 1; i <= N; i++) {
        sort(line[i].begin(), line[i].end());
    }
}

void solve() {
    sort_line();
    dfs(start);
    memset(check, 0, sizeof(check));
    cout << "\n";
    bfs(start);
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> start;
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        line[x].push_back(y);
        line[y].push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!