[백준] DFS와 BFS 1260 (Silver 2) - C++

문제 핵심 요약

• 무방향 그래프
• 정점 번호가 작은 것부터 방문
• 같은 시작점에서
  • DFS 결과 출력
  • BFS 결과 출력

즉, 탐색 알고리즘 + 순서 제어가 핵심입니다.

 

이 문제를 DFS/BFS 템플릿 문제로 두고,
이 구조를 기반으로 다른 그래프 문제들을 풀고 있습니다.

---

DFS / BFS 수도코드 정리

DFS 수도코드 (재귀 기반)

DFS(node):
    node 방문 처리
    node 출력

    for 인접한 정점 next:
        if 방문하지 않았다면:
            DFS(next)

BFS 수도코드 (큐 기반)

queue 생성
시작 노드 push
시작 노드 방문 처리

while queue가 비어있지 않다면:
    현재 노드 pop
    현재 노드 출력

    for 인접한 정점 next:
        if 방문하지 않았다면:
            방문 처리
            queue에 push

이 기본 구조를 코드로 정확히 옮길 수 있으면
대부분의 DFS/BFS 문제는 형태만 바뀔 뿐입니다.

---

그래프 입력 및 정렬 (공통 준비)

vector<vector<int>> graph(n+1); // 1-based

for(int i = 0; i < m; i++){     
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
}

for(int i = 1; i <= n; i++){
    sort(graph[i].begin(), graph[i].end());
}

✔ 정렬이 중요한 이유
→ “정점 번호가 작은 것부터 방문” 조건 때문
→ 탐색 전에 인접 리스트 정렬은 필수 습관

---

❌ Stack으로 DFS 구현 시 흔한 실수

❌ 잘못된 코드 (방문 처리 타이밍 오류)

stack<int> s;
s.push(start);
visited[start] = 1;

while(!s.empty()){
    int a = s.top();
    s.pop();
    visited[a] = 1;   // ❌ pop 이후 방문 처리
    cout << a << " ";

    for(int i : graph[a]){
        if(!visited[i])
            s.push(i);
    }
}

❗ 문제점

• 같은 노드가 여러 번 stack에 들어갈 수 있음
• 중복 push → 불필요한 연산 / 메모리 증가
• 심하면 시간 초과 / 메모리 초과

---

✅ 올바른 Stack DFS의 핵심 규칙

“push할 때 방문 처리”

while(!s.empty()){
    int a = s.top();
    s.pop();
    cout << a << " ";

    for(int i : graph[a]){
        if(!visited[i]) {
            visited[i] = 1;  // ✅ push 직후 방문 처리
            s.push(i);
        }
    }
}

 

⚠️ Stack DFS + 정렬 시 추가로 주의할 점

Stack은 LIFO (후입선출)

• 인접 리스트를 오름차순으로 정렬
• 그대로 push하면
• 큰 숫자가 먼저 pop됨

즉,
👉 재귀 DFS와 같은 순서를 원한다면

• stack에 역순으로 push해야 합니다.

이 문제에서는
👉 재귀 DFS 사용이 가장 안전하고 직관적입니다.

---

최종 정답 코드 (DFS + BFS)

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

vector<vector<int>> graph;
vector<int> visited;

void dfs(int node){
    visited[node] = 1;
    cout << node << " ";
    for(int next : graph[node]){
        if(!visited[next])
            dfs(next);
    }
}

void bfs(int node){
    queue<int> q;
    q.push(node);
    visited[node] = 1;

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        cout << cur << " ";

        for(int next : graph[cur]){
            if(!visited[next]){
                visited[next] = 1;
                q.push(next);
            }
        }
    }
}

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

    int n, m, start;
    cin >> n >> m >> start;

    graph.resize(n+1);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for(int i = 1; i <= n; i++)
        sort(graph[i].begin(), graph[i].end());

    visited.assign(n+1, 0);
    dfs(start);

    cout << "\n";

    visited.assign(n+1, 0);
    bfs(start);
}

---

 

방문 처리와 출력 위치가 헷갈렸던 이유

이 문제를 처음 풀 때 가장 헷갈렸던 부분은
“방문 순서 출력을 언제 해야 하는가”와
“visited 처리를 언제 해야 하는가”였다.

pop 할 때 출력하는데,
그럼 그 시점이 실제로 방문한 순간 아닌가?

그렇다면 visited 처리도 pop 할 때 해도 되는 거 아닌가?

아니면 push 할 때 출력해야 하는 건가?

이렇게 헷갈렸던 이유는
‘방문(visit)’이라는 개념을 물리적인 pop 시점과 동일시했기 때문이다.

핵심 오해: “pop = 방문”이라는 착각

DFS나 BFS에서 중요한 기준은
“언제 노드를 처음 만났는가”이다.

• push (또는 재귀 호출)
  → 이 노드를 처음 발견한 순간
• pop
  → 이미 발견한 노드를 꺼내서 처리하는 순간

이 개념을 놓치면 다음과 같은 문제가 생긴다.

• 같은 노드가 여러 번 자료구조에 들어감
• 출력 순서와 방문 처리 시점이 꼬임
• 특히 stack DFS에서 중복 push 발생

왜 visited는 push 할 때 처리해야 하는가?

만약 visited를 pop 할 때 처리한다면,

• 아직 방문 처리되지 않은 상태로
• 같은 노드가 여러 경로에서
• 여러 번 push 될 수 있습니다.

그래서 DFS, BFS 공통으로 다음 원칙이 성립된다.

자료구조(queue / stack)에 넣는 순간 = 방문 처리

// 올바른 방문 처리 위치
q.push(next);
visited[next] = true;

 

그럼 출력은 언제 해야 할까?

출력은 문제에서 요구하는 “방문 순서”에 따라 달라진다.

BFS / 재귀 DFS

• push 직후와 pop 직후의 순서가 동일
• 그래서 보통 pop 시 출력해도 문제 없음

Stack 기반 DFS

• push 순서 ≠ pop 순서
• 따라서
  • 출력은 pop 시
  • 방문 처리는 push 시
    이 두 역할을 명확히 분리해야 함

// stack DFS 핵심 구조
visited[next] = true;  // 방문 판단
stack.push(next);     // 탐색 예약

 

이 문제를 통해 정리된 기준

이 문제를 풀면서 명확해진 기준은 다음과 같습니다.

• 방문 처리 기준:
  → 처음 발견한 순간 (push / 재귀 호출 시)
• 출력 기준:
  → 문제에서 요구하는 방문 순서에 맞게 pop 또는 함수 진입 시