백준, BOJ, 1260번 C++ [CPP]

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다.

 

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

 

---

 

이것은 그냥 뭐..그냥 구현하면 된다.

 

다만 여기서 주의할 점은

방문을 언제할 것이냐를 판단하느냐 문제다.

나머진 어렵지 않다.

 

그냥 머릿속에서 생각하는 그대로 구현한다.

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

int N, M, V; // 정점, 간선, 시작 노드

int map[1001][1001];
int visited[1001];
int backup[1001];

queue <int> Q;
stack <int> S;



void copy(int origin[1001], int backup[1001]) {
    for (int i = 1; i <= 1000; i++) {
        backup[i] = origin[i];
    }
}



int main() {
    cin >> N >> M >> V;

    for (int i = 0; i < M; i++) {
        int start, end;
        cin >> start >> end;
        map[start][end] = 1;
        map[end][start] = 1;
    }

    //방문자수 백업
    copy(visited, backup);

    visited[V] = 1;
    S.push(V);
    cout << V << " "; // 첫번째 노드 방문
    while (!S.empty()) {
        int cur = S.top();
        S.pop();
        for (int i = 1; i <= N; i++) {
            if (map[cur][i] == 1 && visited[i] == 0) {
                S.push(cur); // 현재 노드를 다시 넣어줘야 하는 이유: DFS는 끝나면 상위 노드로 돌아오면서 탐색해야함
                S.push(i);
                visited[i] = 1;
                cout << i << " "; 
                break; // 스택에 전부 넣는 것이 아니라 최초로 발견된 노드만 넣음
            }
        }
    }


    cout << "\n" ;
    //초기화
    copy(backup, visited);

    visited[V] = 1;
    Q.push(V);
    cout << V << " ";
    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        for (int i = 1; i <= N; i++) {
            if (map[cur][i] == 1 && visited[i] == 0) {
                Q.push(i);
                visited[i] = 1;
                cout << i << " "; // DFS와 다르게 전부 넣고 전부 차례대로 방문하기 때문임
            }
        }
    }

}