[알고리즘] 백트래킹

내 인생은 거꾸로 트래킹 중...
에휴... 내 인생 어카냐....

뭐 농담으로 거꾸로 트래킹이란 말을 적어놨지만...
백트래킹은 말 그대로 뒤(역)로 올라가는 알고리즘이다.

📃 예시 문제

[프로그래머스] - 단어 변환

이 문제를 지금 앞서 말한 백트래킹을 통해 제출했다.
근데... 이거 코테 문제들을 풀어보면서 많이 봤던 코드 중, 한 부분인데...

public void dfs(String current, String target, String[] words, int depth) {
    if (current.equals(target)) {
        ans = Math.min(ans, depth);
        return;
    }

    for (int i = 0; i < words.length; i++) {
        if (!visited[i] && cntDifferentChar(current, words[i])) {
            visited[i] = true;
            dfs(words[i], target, words, depth + 1);
            visited[i] = false;
        }
    }
}

조기 for문 안에

visited[i] = true;
dfs(words[i], target, words, depth + 1);
visited[i] = false;

요부분이 백트레킹 부분이다.

📍설명

일단 문제의 답은 그래프가 cog라는 단어를 찍고 와야 정상인데,
순번상 lot부터 찍어버린다...;;

lot는 답이 아니기 때문에, 다시 log로 돌아가서 cog를 찍게 된다.

즉, 재귀를 통해 확인 중인 노드(상태)가 조건에 위배되는지 판단하고,
제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다.

우측 그림으로 설명하면, 3번 노드를 탐색했지만 어떠한 조건이 맞지 않았고, 부모 노드인 1번으로 돌아가서 그 다음 4번 노드를 탐색하는 방식이다.

visited[i] = true; // 자식 노드 방문처리~
dfs(words[i], target, words, depth + 1); // 자식 노드 방문!
visited[i] = false; // 자식 노드 방문 취소...

자식 노드를 방문을 했는데, 문제 조건에 위배
그래서 방문을 취소하는 코드..

백트레킹의 핵심 코드다.

❔그럼 어떤 유형이 백트래킹을 써야돼...?

1. 모든 경우를 탐색

→ 경우의 수가 많다
→ 전부 해봐야 하는데 조건을 만족하지 않으면 중간에 가지를 쳐낼 수 있음
백트래킹!

2. 조건을 만족하는 경우만 탐색

→ 제한 조건을 만족하는 조합/배열/경로
→ (합이 M이 되는 부분집합을 모두 출력)

문제를 좀 읽어 보다가, 탐색하고, 조건에 맞는 답을 구하라.
즉, 가지치기를 하라고 하면 아마 백트레킹 문제 같다!