[Do it! 알고리즘 코딩 테스트 자바] 백트래킹을 써야하는 이유(feat.DFS) - 백준 11724/2023/13023/15649/9663(10일차)

DFS와 백트래킹 개념 및 차이

• DFS 개념: 그래프나 트리 구조에서 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 완전 탐색 방식.
• 백트래킹 개념: 탐색 과정 중 현재 경로가 조건에 맞지 않으면 더 이상 깊이 들어가지 않고 이전 상태로 돌아가 다른 경로를 찾는 알고리즘 기법.
• 둘의 차이점: DFS는 조건과 무관하게 모든 노드를 맹목적으로 방문함. 백트래킹은 DFS를 기반으로 하되 유망하지 않은 노드는 사전에 배제(가지치기)함.
• 백트래킹을 많이 쓰는 이유: 불필요한 탐색 경로를 조기에 차단하여 경우의 수가 폭발적으로 증가하는 문제의 실행 시간을 기하급수적으로 줄일 수 있기 때문임.

---

 

[11724번: 연결 요소의 개수]

• 고려 내용: 양방향 간선의 그래프 표현 및 방문 여부 체크 방식.
• 문제 핵심: 방문 배열을 활용한 기본적인 깊이 우선 탐색 및 재귀 로직의 이해.
• 최적화 및 결과: ArrayList를 활용한 인접 리스트 구현 및 기초적인 DFS 구조 확립.

[2023번: 신기한 소수]

• 고려 내용: 자리수를 늘려가며 매번 소수 여부를 판별하는 방법.
• 문제 핵심: 이전 자리까지의 숫자가 소수일 때만 다음 자리수로 재귀 탐색 진행.
• 최적화 및 고려사항:
  • 비효율적인 문자열: 자리수를 늘릴 때 문자열(String) 결합을 사용하고 매번 정수로 변환함. -> 정수 연산 사용: 메모리 낭비와 형변환 오버헤드를 막기 위해 (기존 숫자 * 10 + 새로운 숫자) 방식의 수학적 연산 채택.
  • 소수 판별 알고리즘 최적화: 소수 판별 시 N/2까지 반복문을 돌아 불필요한 연산이 많았음. -> 제곱근까지만 확인(i * i <= num)하여 시간 복잡도를 O(N)에서 O(sqrt{N})으로 기하급수적으로 단축함. (약수는 대칭을 이룸)

[13023번: ABCDE]

• 고려 내용: 특정 시작점이 정해져 있지 않으므로 모든 노드에서의 출발 가능성 고려 및 깊이 5 도달 여부 파악.
• 문제 핵심: 탐색이 막혀 돌아올 때 다른 경로 탐색을 위해 방문 기록을 다시 해제(visited = false)하는 백트래킹 기법 적용.
• 최적화 및 고려사항:
  • 모든 사람을 시작점으로 (main): 누가 첫 번째 노드일지 모르므로, main 함수에서 모든 노드에 대해 무조건 DFS를 출발시켜야 함. (이때는 방문여부 조건 보지 않음)
  • 시작 노드 방문 기록 지우기: DFS 종료 후 자기 자신의 방문 기록을 지우지 않아 다른 경로의 탐색을 차단함.  -> 탐색을 마치고 뒤로 돌아갈 때(return 직전), 현재 노드의 visited[i] = false 처리를 통해 발자국을 지워야 함.
  • 조기 종료: 종료 조건을 메서드 하단에 배치하여 불필요한 연산이 발생함. -> 정답을 찾았거나 깊이(depth)가 목표에 도달했다면, 메서드 최상단에서 즉시 return 시켜 콜 스택의 낭비를 막음.

[15649번: N과 M (1)]

• 고려 내용: 중복 없는 순열 생성을 위한 배열 인덱스와 삽입 값의 논리적 구분.
• 문제 핵심: depth 변수를 배열의 인덱스로 활용하여 순차적으로 값을 채우는 백트래킹 기본 구조.
• 최적화 및 고려사항:
  • 수동 호출 제거: main 메서드에서 첫 번째 자리를 수동으로 채우고 반복문으로 DFS를 호출하여 구조가 복잡해짐.  -> main에서는 DFS(0) 단 한 번만 호출. 재귀 함수 내부의 for문이 0번째 자리부터 마지막 자리까지 스스로 채우도록 역할을 온전히 위임함.
  • 방문 처리(visited) 위치 표준화: 방문 처리 로직의 위치가 파편화됨. ->  visited[i] = true -> DFS(depth + 1) -> visited[i] = false 의 순서로 재귀 호출을 위아래로 감싸는 백트래킹의 가장 표준적인 템플릿 구조를 확립함.

[9663번: N-Queen]

• 고려 내용: 2차원 배열 대신 1차원 배열(인덱스=행, 값=열)을 활용한 상태 압축. 세로열 및 대각선 공격 범위 파악.
• 문제 핵심: 바로 윗줄뿐만 아니라 0번째 행부터 이전까지 놓인 모든 퀸과 현재 위치의 퀸이 대각선 방향으로 겹치는지 수학적 검증(행의 차이의 절댓값과 열의 차이의 절댓값 비교).
• 최적화 및 고려사항:
  • 모든 윗줄 검사: 대각선 검사 시 내 '바로 윗줄' 하나만 확인하여 경우의 수가 폭발함. -> 현재 놓으려는 퀸의 위치가 안전한지 확인하려면, 0번째 줄부터 내 바로 윗줄(depth - 1)까지 놓인 모든 퀸과 비교해야 함.
  • 대각선 겹침 확인 수학 공식: 가로 간격과 세로 간격이 같으면 대각선임. Math.abs(현재 행 - 과거 행) == Math.abs(현재 열 - 과거 열) 공식을 활용하여 좌우 대각선을 모두 방어함.
  • 대각선 여부 검사 메서드 분리: 대각선 반복 검사인 for문 내부에서 즉시 재귀를 호출하던 구조적 오류 수정. -> 복잡한 조건 검사는 isPossible(depth) 같은 별도의 판별 메서드로 분리. 검사 통과 -> 방문 처리 -> 다음 줄 이동 -> 백트래킹의 깔끔한 흐름을 구축함.