[코드트리] 백트래킹 알고리즘 약점 극복 학습 후기

1회차에서 진행했던 갭체크 결과를 기반으로 이번 주에는 나의 약점 중 하나였던 백트래킹 트랙을 집중적으로 학습했습니다.

코드트리 플랫폼은 주제별로 단계적인 개념 설명과 문제들이 체계적으로 준비되어 있어, 기초부터 응용까지 차근차근 학습하기에 매우 좋았습니다. 이번 포스팅에서는 백트래킹 트랙을 진행하며 가장 인상 깊었고 까다로웠던 문제를 하나 소개하고 풀이를 정리해보려 합니다.

문제: 2명의 도둑

• 링크: 2명의 도둑
• 알고리즘 분류: 완전 탐색(Brute Force), 비트마스킹(Bitmasking), 조합론(Combinatorics)

문제 설명

2명의 도둑이 N * N 크기의 방에서 물건을 훔치려 합니다. 두 도둑은 각각 하나의 행을 정해 그 행 내에 연속한 M개의 열에 있는 물건들을 훔칠 수 있습니다.

[조건]

1. 두 도둑이 같은 행을 고를 수는 있지만, 같은 행을 골랐을 때에는 선택한 M개의 열이 서로 겹쳐서는 안 됩니다.
2. 각 도둑은 자신이 선택한 M개의 물건 중 적절히 골라 무게의 합이 C를 넘지 않도록 해야 합니다.
3. 이때 가치는 고른 물건들의 무게의 제곱의 합이 됩니다.

[입력/출력]

• 입력: 첫째 줄에 방의 크기 N, 연속으로 훔칠 수 있는 열의 개수 M, 각 도둑이 훔칠 수 있는 최대 무게 C가 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 방에 있는 물건들의 무게가 주어집니다.
• 출력: 두 도둑이 얻을 수 있는 가치의 총합 중 최댓값을 구하는 프로그램을 작성합니다.

풀이: 4중 반복문과 비트마스킹을 활용한 최적 가치 탐색

이 문제는 방의 크기 N이 10 이하로 매우 작다는 점이 핵심입니다. 따라서 4중 반복문을 이용해 두 도둑의 시작 위치를 모두 완전 탐색하고, 각 위치에서 M개의 물건 중 일부를 고르는 경우의 수를 비트마스킹으로 해결하는 복합 완전 탐색 풀이로 접근했습니다.

1. 두 도둑의 위치 선정 (4중 반복문)

도둑 1의 시작점 (y1, x1)과 도둑 2의 시작점 (y2, x2)를 모두 순회합니다. M개의 연속된 물건을 훔쳐야 하므로 열의 인덱스 제한은 x <= n - m으로 설정합니다.

2. 겹침 방지 검사

가장 중요한 조건 중 하나입니다. 두 도둑이 같은 행(y1 == y2)에 있을 때, 한 도둑의 구간이 다른 도둑의 구간을 침범하는지 확인해야 합니다. '첫 번째 선분이 아예 왼쪽에 있거나, 아예 오른쪽에 있는 경우'를 제외한 나머지는 모두 겹치는 경우이므로, !(x1 + m - 1 < x2 || x2 + m - 1 < x1) 라는 논리식을 사용하여 겹침을 정확히 잡아내어 해당 케이스는 건너뜁니다(continue).

3. 부분 집합의 최대 가치 도출 (비트마스킹)

겹치지 않는 유효한 두 위치를 찾았다면, getValue(y, x) 메서드를 통해 해당 구간에서 도둑이 훔칠 수 있는 최대 가치를 계산합니다. 한 도둑이 훔칠 수 있는 물건의 개수 M 역시 제한이 작으므로, 1 << m까지 반복하며 부분 집합을 비트마스킹으로 구현합니다. (해당 비트가 1이면 훔치고 0이면 훔치지 않음)

비트가 켜진 물건들의 무게(w)를 더하고, 제한 무게 C 이하일 때만 가치(v += 무게 * 무게)를 누적하여 해당 구간의 최댓값(ret)을 갱신합니다.

4. 최댓값 갱신

각 도둑이 얻을 수 있는 가치의 합(getValue(y1, x1) + getValue(y2, x2)) 중 가장 큰 값을 정답 변수 ans에 지속적으로 갱신하여 최종 반환합니다.

 Java 제출 코드

import java.util.*;
import java.io.*;

public class Main {
    static int n, m, c;
    static int[][] a;

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       n = Integer.parseInt(st.nextToken());
       m = Integer.parseInt(st.nextToken());
       c = Integer.parseInt(st.nextToken());

       a = new int[n][n];
       // 1. 방의 정보 입력
       for (int i = 0; i < n; i++) {
          st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++) {
             a[i][j] = Integer.parseInt(st.nextToken());
          }
       }

       int ans = 0;

       // 2. 도둑 1과 도둑 2의 시작 위치를 모두 탐색하는 4중 반복문
       for (int y1 = 0; y1 < n; y1++) {
          for (int x1 = 0; x1 <= n - m; x1++) {
             for (int y2 = 0; y2 < n; y2++) {
                for (int x2 = 0; x2 <= n - m; x2++) {

                   // 같은 행일 때 M칸 구간이 겹치는지 검사
                   if (y1 == y2 && !(x1 + m - 1 < x2 || x2 + m - 1 < x1)) {
                      continue;
                   }

                   // 겹치지 않는다면 두 구간의 가치 합산 후 최댓값 갱신
                   ans = Math.max(ans, getValue(y1, x1) + getValue(y2, x2));
                }
             }
          }
       }

       bw.write(ans + "");
       bw.flush();
    }

    // 주어진 시작 위치(y, x)에서 M칸 중 C 이하로 고를 수 있는 최대 가치 계산
    static int getValue(int y, int x) {
       int ret = 0;

       // M개의 물건에 대한 모든 부분 집합 탐색 (비트마스킹)
       for (int i = 1; i < (1 << m); i++) {
          int w = 0;
          int v = 0;

          for (int j = 0; j < m; j++) {
             // i번째 상태에서 j번째 물건을 훔친다면
             if ((i & (1 << j)) != 0) {
                w += a[y][x + j];
                v += a[y][x + j] * a[y][x + j];
             }
          }

          // 무게 합이 제한 C 이하일 때만 가치 갱신
          if (w <= c) {
             ret = Math.max(ret, v);
          }
       }

       return ret;
    }
}

마무리

이번 주차 학습을 통해 복잡해 보이는 조건들도 부분적으로 쪼개어 완전 탐색과 비트마스킹을 결합하면 깔끔하게 해결할 수 있다는 것을 배웠습니다. 특히 1차원 선분의 겹침 여부를 판단하는 논리식은 다른 문제에서도 유용하게 쓰일 것 같습니다.

체계적인 커리큘럼 덕분에, 이전에는 막막하게만 느껴졌던 백트래킹과 완전탐색 문제들에 대해 이제는 꽤 자신감이 붙었습니다. 남은 챌린지 기간 동안 다른 취약점인 DP도 이 기세로 확실히 정복해 보겠습니다.

https://www.codetree.ai

Codetree: Master Coding Interviews - Data Structures & Algorithms