BFS에서 visited를 push할 때 찍어야 하는 이유

결론

• BFS: visited를 push할 때 찍는다
• DFS: visited를 재귀 진입 시 찍는다

이유는 큐에 넣는 시점과 꺼내는 시점 사이의 시간 차 때문이다.

---

BFS: pop할 때 찍으면 생기는 문제

A와 B가 큐에 들어있고, 둘 다 C의 이웃이라고 하자.

큐: [A, B]

1. pop A → C 미방문 → push C       큐: [B, C]
2. pop B → C 아직 미방문 → push C   큐: [C, C]  ← 중복

A가 C를 push했지만 visited를 안 찍었으므로, B가 C를 볼 때도 미방문이다. C가 큐에 두 번 들어간다.

격자에서는 한 칸을 최대 4방향 이웃이 동시에 발견할 수 있다. 중복 push는 큐 크기를 불필요하게 키우고, 같은 칸을 여러 번 처리하여 시간 초과를 유발한다.

BFS: push할 때 찍으면

큐: [A, B]

1. pop A → C 미방문 → visited[C]=true, push C   큐: [B, C]
2. pop B → C 이미 방문 → skip                    큐: [C]

C는 큐에 한 번만 들어간다.

---

DFS: 재귀 진입 시 찍어도 되는 이유

dfs(A)
  → visited[A] = true
  → dfs(C)               ← 발견 즉시 재귀 진입
       → visited[C] = true
       → ...
  → (돌아옴) C 이미 방문 → skip

DFS는 C를 발견하면 즉시 재귀로 들어가서 visited[C] = true를 찍는다. “발견 → 처리” 사이에 다른 노드가 끼어들 틈이 없다. 호출 스택 자체가 한 노드에 하나의 진입만 보장한다.

BFS는 큐에 넣고 나중에 꺼내므로, 그 사이에 다른 노드가 같은 칸을 또 발견할 수 있다. 이것이 근본적인 차이다.

---

코드 비교

BFS (push 시 마킹)

queue<Node> q;
q.push({0, 0, 1});
visited[0][0] = true;       // push와 동시에

while (!q.empty()) {
    auto [x, y, dist] = q.front();
    q.pop();

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (/* 범위 밖 */) continue;
        if (visited[nx][ny] || maps[nx][ny] == 0) continue;

        visited[nx][ny] = true;  // push 전에 마킹
        q.push({nx, ny, dist + 1});
    }
}

DFS (진입 시 마킹)

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;        // 진입과 동시에

    for (int next : adj[node]) {
        if (!visited[next])
            dfs(next, adj, visited);
    }
}

---

정리

	BFS	DFS
visited 시점	push할 때	재귀 진입 시
이유	push-pop 사이 시간 차로 중복 가능	발견 즉시 진입, 끼어들 틈 없음
안 지키면	중복 push → 시간 초과	문제 없음 (구조적으로 중복 불가)