[백준] 13023 - 백트래킹 적용하기

들어가며

안녕하세요, 오늘은 DFS(깊이 우선 탐색)와 백트래킹을 활용하여 친구 관계 탐색 문제를 해결하는 과정을 단계별로 살펴보겠습니다. dfs, bfs 문제를 풀고 백트래킹 문제를 풀려고 했는데 이렇게 바로 풀게 되었습니다.

🤔 Before: 처음 마주친 문제 상황

문제는 다음과 같습니다:

• N명의 사람들 사이의 친구 관계가 주어집니다.
• 한 사람에서 시작하여 친구 관계를 4번 이상 거쳐갈 수 있는지 확인해야 합니다.
• 가능한 경로가 존재하면 1, 없으면 0을 출력합니다.

처음에는 단순히 DFS를 구현하면 될 것이라 생각했지만, 여러 문제점들에 직면했습니다:

1. 한 시작점에서만 탐색을 시작하여 모든 가능한 경로를 찾지 못했습니다.
2. 메모리를 많이 사용하는 인접 행렬 방식을 사용했습니다.
3. 이전 경로로 돌아가서 다른 경로를 탐색하는 백트래킹이 없었습니다.

🎯 After: 이상적인 해결 방안

최적의 해결책은 다음과 같은 특징을 가져야 합니다:

1. 모든 정점에서 시작하여 가능한 모든 경로를 탐색할 수 있어야 합니다.
2. 메모리를 효율적으로 사용하는 인접 리스트 방식을 사용해야 합니다.
3. 백트래킹을 통해 이전 상태로 돌아가 다른 경로도 탐색할 수 있어야 합니다.
4. 방문 체크와 깊이 체크가 명확하게 구분되어야 합니다.

🌉 Bridge: 문제 해결 과정

1️⃣ 첫 번째 시도: 기본적인 DFS 구현

let graph = Array.from({ length: N }, () => Array(N).fill(0));
function dfs(x, depth) {
  result[x] = depth;
  for (let i = 0; i < N; i++) {
    if (graph[x][i] === 1 && result[i] === 0) {
      dfs(i, depth + 1);
    }
  }
}
dfs(0, 1);

이 구현의 한계점:

• 하나의 시작점(0번 정점)에서만 탐색을 시작합니다.
• 인접 행렬 방식으로 불필요한 메모리를 사용합니다.
• 방문했던 경로를 다시 탐색할 수 없습니다.

2️⃣ 두 번째 시도: 모든 정점에서 탐색 시작

let answer = 0;
for (let i = 0; i < N; i++) {
  dfs(i, 1);
  answer = Math.max(...result);
  if (answer >= 5) {
    answer = 1;
    break;
  }
  result = Array(N).fill(0);
}

개선된 점:

• 모든 정점에서 DFS를 시작합니다.
• 각 시작점마다 결과 배열을 초기화합니다.

여전한 문제점:

• 백트래킹이 없어 이전 경로로 돌아갈 수 없습니다.
• 깊이 체크 방식이 부정확합니다.

3️⃣ 세 번째 시도: 인접 리스트와 백트래킹 도입

let graph = Array.from({ length: N }, () => []);
function dfs(x, depth) {
  result[x] = depth;
  for (let i = 0; i < graph[x].length; i++) {
    let neighbor = graph[x][i];
    if (result[neighbor] === 0) {
      dfs(neighbor, depth + 1);
      result[neighbor] = 0; // 백트래킹 시도
    }
  }
}

개선된 점:

• 인접 리스트 방식으로 메모리 효율성이 개선되었습니다.
• 백트래킹을 시도했습니다.

남은 문제점:

• 백트래킹 구현이 불완전합니다.
• 방문 체크와 깊이 체크가 혼재되어 있습니다.

4️⃣ 최종 해결책: 완전한 백트래킹 구현

function dfs(current, depth, visited) {
  if (depth === 5) {
    return true;
  }

  for (let next of graph[current]) {
    if (!visited[next]) {
      visited[next] = true;
      if (dfs(next, depth + 1, visited)) return true;
      visited[next] = false;
    }
  }
  return false;
}

최종 개선사항:

• 방문 배열을 통한 명확한 상태 관리
• 완전한 백트래킹 구현
• 목표 깊이 도달 시 즉시 반환
• 각 경로의 독립적인 탐색 보장

💡 백트래킹 구현의 핵심 포인트

1. 상태 관리의 중요성

백트래킹에서 가장 중요한 것은 상태 관리입니다. 방문 배열을 통해 각 노드의 방문 상태를 추적하고, 탐색이 끝난 후에는 반드시 상태를 원복해야 합니다.

visited[next] = true;  // 방문 표시
dfs(next, depth + 1, visited);
visited[next] = false; // 방문 해제

2. 목표 조건 확인

깊이가 목표에 도달했는지 확인하고, 조건을 만족하면 즉시 반환하여 불필요한 탐색을 방지합니다.

if (depth === targetDepth) {
  return true;
}

3. 재귀 호출과 상태 복원의 대칭성

재귀 호출 전후로 상태 변경과 복원이 대칭적으로 이루어져야 합니다.

for (let next of graph[current]) {
  // 상태 변경
  visited[next] = true;
  // 재귀 호출
  if (dfs(next, depth + 1, visited)) return true;
  // 상태 복원
  visited[next] = false;
}

🎓 배운 점

이 문제를 해결하면서 몇 가지 중요한 교훈을 얻었습니다:

1. 점진적 개선의 중요성: 한 번에 완벽한 해결책을 만들기는 어렵습니다. 단계적으로 문제를 해결하고 개선해 나가는 것이 효과적입니다.
2. 자료구조의 선택: 인접 행렬에서 인접 리스트로의 전환을 통해 메모리 효율성을 크게 개선할 수 있었습니다.
3. 백트래킹의 필요성: 모든 가능한 경로를 탐색해야 하는 문제에서는 백트래킹이 필수적입니다.
4. 상태 관리의 중요성: 방문 상태와 깊이를 명확하게 관리하는 것이 알고리즘의 정확성을 보장합니다.

🔚 마치며

DFS와 백트래킹을 활용한 문제 해결 과정을 통해, 알고리즘 구현에서 중요한 여러 개념들을 실제로 적용해볼 수 있었습니다. 특히 백트래킹의 개념을 정확히 이해하고 구현하는 것이 이러한 유형의 문제를 해결하는 데 핵심임을 알 수 있었습니다.