Skip to main content

[Java] DFS와 BFS에서 방문 체크 위치

1. 방문 체크

visited[node] = true;

DFS/BFS에서 이 코드가 들어가는 위치가 다르다

2. DFS (재귀)

void dfs(int node) {
    visited[node] = true; // ✅ 방문 체크: 재귀 들어오자마자
    System.out.print(node + " ");
    
    for(int next : graph[node]) {
        if(!visited[next]) {
            dfs(next); // 재귀 호출
        }
    }
}
  • DFS에서 핵심은 노드를 처리(출력)하기 전에 방문 체크하는 것이다.
  • 재귀를 들어가기 전에 dfs 메서드 시작하자 마자 방문체크를 한다,.
  • 왜? 체크를 늦게 하면 이미 스택 안에서 같은 노드를 다시 방문할 수 있고 그러면 무한 루프에 빠지기 때문이다.
  • 즉, for문에서 재귀호출하는 시점에서는 별도로 방문체크 하지 않는다 (BFS랑 차이점)

3. BFS(큐)

void bfs(int start) {
    Queue<Integer> q = new LinkedList<>();
    visited[start] = true;       // ✅ 방문 체크: 큐에 넣을 때
    q.add(start);

    while(!q.isEmpty()) {
        int node = q.poll();
        System.out.print(node + " ");

        for(int next : graph[node]) {
            if(!visited[next]) {
                visited[next] = true; // ✅ 큐에 넣으면서 방문 체크
                q.add(next);
            }
        }
    }
}
  • BFS는 방문체크가 2번이다.
  • 큐에 노드를 넣기 전(eunqueue)에 방문 체크를 한다.
  • 이렇게 하면 같은 노드가 큐에 두 번 들어가는 걸 방지할 수 있다.
  • 즉, q.add() 코드 쓰기 직전에는 방문체크 먼저 한다고 생각하기

잘못된 사용 :

q.add(next);           // 먼저 넣고
...
node = q.poll();
visited[node] = true;  // 나중에 체크
  • 아직 방문하지 않은 상태이기 때문에 이미 큐에 들어간 같은 노드가 또 들어갈 수 있음

그럼 큐에 넣는 순간 방문 체크를 안 하면 어떻게 되는지 아래 예시로 살펴 보자. 아래와 같은 그래프가 있다면

1 - 2
1 - 3
2 - 3
  • 시작점: 1
  1. 1에서 인접 노드 2와 3을 큐에 넣음 → 아직 방문 체크 안 함
  2. 2에서 인접 노드 1과 3을 또 큐에 넣음 → 3이 이미 큐에 있지만 체크를 안 해서 또 들어감
  3. 3도 마찬가지로 여러 번 들어갈 수 있다

즉, 큐 안에 같은 노드가 중복으로 들어가는 상황이 발생한다.



Back to top