백트래킹(Back Tracking)

1. 백트래킹이란?

이전까지의 DFS (참고: https://roajava.tistory.com/262)

• 지나가는 길에 표시를 한다. (visited = true)
• 막다른 길을 만나서 되돌아 올 때, 그 표시를 지우지 않는다.
• 결과 : 한 번 지나간 곳은 영원히 다시 못감

 

백트래킹(Back Tracking)

• 지나가는 길에 표시를 한다. (visited = true)
• 막다른 길을 만나서 되돌아 올 때, 표시한 흔적을 지운다. (visited = false)
• 결과 : 한 번 지나갔던 곳이라도 나왔다면 다시 방문할 수 있음.

백트래킹은 DFS + 취소(Undo) 기능이다.

 

 

2. 코드 차이

DFS의 핵심 로직 예시

void dfs(int x, int y) {
    visited[x][y] = true; // 1. 방문 도장 쾅! (영구적)
    
    for (int i=0; i<4; i++) {
        // ... 다음 좌표 nx, ny ...
        if (!visited[nx][ny]) {
            dfs(nx, ny); // 2. 더 깊이 들어감
        }
    }
    // (끝. 되돌아나올 때 아무것도 안 함. visited는 true로 남음)
}

 

 

백트래킹 핵심 로직

void dfs(int x, int y) {
    visited[x][y] = true; // 1. 방문 도장 쾅! (잠시만)
    
    for (int i=0; i<4; i++) {
        // ... 다음 좌표 nx, ny ...
        // 가지치기 (Pruning): "이 길은 가망이 있어?" 확인
        if (조건에_맞으면) { 
            dfs(nx, ny); // 2. 더 깊이 들어감
        }
    }

    // ★ 여기가 핵심 ★
    // 함수가 끝나고(막다른 길) 부모에게 돌아가기 직전에
    // "나 여기 안 왔던 셈 쳐줘!" 하고 도장을 지움
    visited[x][y] = false; 
}

 

 

3. 백트래킹의 특징 및 정리

백트래킹의 또 다른 핵심은 가지치기를 한다는 것이다.

• 탐색하다가 이 길이 정답이 아니라고 판단이되면 더 이상 깊게 안들어가고 바로 return을 한다.
• 이 방법을 사용해야 시간초과가 나지 않는다.

백트래킹은 상태를 저장(visited = true)하고, 재귀 함수를 돌고, 다시 복구(visited = false)하는 기법이다.