(C++) 백준 1260번 [DFS와 BFS]

오랜만에 그래프 문제를 풀었다.

그래서 그런지 조금 낯설었지만 기본적인 문제라 나름 괜찮았다.

아주 전형적이고 기본적인 DFS, BFS문제라 가볍게 풀어보기 좋은 것 같다.

 

실버2 난이도

 

 

---

1. 문제 해결방법 구상

- DFS는 스택을 이용, BFS는 큐를 이용. (DFS에서 굳이 스택을 이용하지 않고 재귀를 이용해도 됨, 근데 한번 스택으로 구현해보았다.)
- DFS와 BFS의 관건은 언제 노드 방문 처리를 하고, 컨테이너에서 노드를 pop하는 지를 잘 고민해야함.
- DFS에서 스택을 이용해서 구현을 한다면, 더 이상 깊은 depth로 갈 수 없을 때( 더이상 edge가 없는 node에 이르렀을 때)를 어떻게 처리해주느냐가 중요.
- 뿐만 아니라 부모 노드로 다시 돌아갔을 때, 갈 수 있는 또 다른 node가 있는 지를 확인해줘야 하므로 이를 잘 처리해야 함.

---

2. 해결 방법 구상에 따라 코드 구현

#include <bits/stdc++.h>
using namespace std;

int N, M, V;
vector<vector<int>> edge(1001);
// vector가 아닌 int 배열로 2차원 [1001][1001]로 해도 되지만
// 그렇게 하면 갈 수 있는 노드를 확인할 때 모든 node에 대해 확인해야 하므로
// 불필요한 시간을 소모함. 따라서 vector로 구현
bool visit_DFS[1001] = {false, };
bool visit_BFS[1001] = {false, };  // 그냥 memset안해주고 따로 둠

void DFS(int v) {
    stack<int> s;
    s.push(v);
    bool nowhere = true;
    visit_DFS[v] = true;
    cout << v << " ";

    while(!s.empty()) {
        int top = s.top();
        nowhere = true;
        // nowhere은 해당 노드에서 갈 node가 없는 경우 확인을 위한 flag
        for(int i = 0; i < edge[top].size(); i++) {
            if (!visit_DFS[edge[top][i]]) {
                int n_node = edge[top][i];
                s.push(n_node);
                visit_DFS[n_node] = true;
                cout << n_node << " ";
                nowhere = false;
                break;
            }
        }
        if (nowhere) {
            s.pop();
        }
    }
}

void BFS(int v) {
    queue<int> q;
    q.push(v);

    while(!q.empty()) {
        int f = q.front();
        q.pop();
        if (visit_BFS[f])  continue;
        visit_BFS[f] = true;
        cout << f << " ";
        for(int i = 0; i < edge[f].size(); i++) {
            if (!visit_BFS[edge[f][i]]) {
                q.push(edge[f][i]);
            }
        }
    }
}

int main() {
    cin >> N >> M >> V;
    for(int i = 0; i < M; i++) {
        int n1, n2;
        cin >> n1 >> n2;
        edge[n1].push_back(n2);
        edge[n2].push_back(n1);
    }
    for(int i = 0; i < edge.size(); i++) {
    	// vector로 edge를 구현했으므로 노드를 
        // 노드의 숫자순으로 오름차순 정렬해주어야 한다.
        sort(edge[i].begin(), edge[i].end());
    }
    DFS(V);
    cout << endl;
    BFS(V);
}

---

3. 느낀 점

기본적인 DFS, BFS 뿐만 아니라 그래프 개념을 적용한 복잡한 문제도 접해볼 필요가 있다고 느꼈다.

그리고 많은 코테 문제들이 DP와  그래프가 주가 되기 때문에 그래프 문제를 더 자주 접하는 게 중요한 것 같다.

 

 

//문제제기 및 피드백 언제든지 감사히 받겠습니다.​