[백준(BOJ)] 1260번 : DFS와 BFS - C++[CPP]

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

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

DFS와 BFS 알고리즘을 사용하여 푸는 문제이다.

 

DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색이다.

 

DFS의 구현은 스택 또는 재귀 함수로 구현한다.

BFS의 구현은 큐를 이용해서 구현한다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>

using namespace std;

int n,m,v;

int arr[1001][1001];
bool visit[1001];

void reset_visit() {
    for (auto i=1;i<=n;i++) {
        visit[i]=false;
    }
}

void dfs(int v) {
    visit[v]=true;
    cout << v << " ";
    
    for(int i=1;i<=n;i++) {
        if (visit[i]==1 || arr[v][i]==0)
            continue;
        dfs(i);
    }
}

void bfs(int v) {
    queue<int> q;
    q.push(v);
    visit[v]=true;
    cout << v << " ";

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

        for(auto i=1;i<=n;i++) {
            if (arr[v][i]==1 && visit[i]==0) {
                q.push(i);
                visit[i] = true;
                cout << i << " ";
            }
        }
    }
}

int main() {
    cin >> n >> m >> v;
    for(auto i =0;i<m;i++) {
        int x,y;
        cin >> x >> y;
        arr[x][y]=1;
        arr[y][x]=1;
    }

    reset_visit();
    dfs(v);
    cout<<"\n";
    reset_visit();
    bfs(v);
}

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!