[BOJ] #1260 DFS와 BFS

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

1260번: DFS와 BFS

---

이전에 한번 게시했던 문제인데, 애초에 백준 계정을 새로 파서 푼 흔적이 없어졌기 때문에 한번 더 풀었고, 최근에 DFS랑 BFS 개념을 다시 복습하면서 다시 한번 풀어보았다. 문제 자체에서 어려운점은 크게 없었던 것 같다. 그래프를 인접리스트 형태로 주어지는대로 입력받고 입력받은 그래프를 토대로 각각 DFS와 BFS를 적용하여 풀어내면 되는 문제이다.

필자는 인접리스트 형태로 받는 과정에서 vector를 사용해서 풀긴 했는데, 중간에 정렬하는 과정이 들어가기 때문에 그냥 pair<int,int>형 set을 사용해도 되지 않을까..? 싶었다. 하지만 그냥 손에 익은게 vector이기에,,, 그냥 그걸로 풀었다. set이랑 map도 좀 익숙해져야 하는데 도통 잘 되지않는다. 특히 map이 매우 편리한 자료구조인데.. 계속 더 연습해야겠다.

다만 첫번째 시도에서 틀렸습니다가 떴고 두번째에서는 OutofBound 런타임에러가 떴는데, 처음엔 문제를 잘 안읽어서... [단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,] 이 항목을 제대로 안읽고 그냥 풀었다. 그리고 두번째에는 입력받은 인접리스트 벡터를 정렬하는 과정에서 할당되지 않은 인덱스까지 접근하여 정렬하려 했기때문에 런타임에러가 난 듯 하다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> Graph[1005];
bool D_visited[1005];
bool B_visited[1005];

void DFS(int start) {
    D_visited[start] = true;

    cout << start << ' ';

    for (int i=0; i<Graph[start].size(); i++) {
        int idx = Graph[start][i];

        if (!D_visited[idx]) DFS(idx);
    }
}

void BFS(int start) {
    queue<int> Q;
    Q.push(start);
    B_visited[start] = true;

    while(!Q.empty()) {
        int n = Q.front();
        Q.pop();
        cout << n << ' ';

        for (int i=0; i<Graph[n].size(); i++) {
            int idx = Graph[n][i];

            if (!B_visited[idx]) {
                Q.push(idx);
                B_visited[idx] = true;
            }
        }
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int N,M,V;
    cin >> N >> M >> V;

    while(M-->0) {
        int x,y;
        cin >> x >> y;

        Graph[x].push_back(y);
        Graph[y].push_back(x);

        sort(Graph[x].begin(), Graph[x].end());
        sort(Graph[y].begin(), Graph[y].end());
    }

    DFS(V);
    cout << '\n';
    BFS(V);
    cout << '\n';

    return 0;
}