15684번: 사다리 조작

문제

사다리 게임에서 i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려고 합니다. 주어진 사다리 정보에 가로선을 추가하여 조작하되, 두 가로선이 연속하거나 서로 접하면 안 됩니다. 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하는 문제입니다. 만약 정답이 3보다 크거나 불가능한 경우 -1을 출력합니다.

• 입력: 세로선의 개수 N (2 ≤ N ≤ 10), 가로선의 개수 M (0 ≤ M ≤ (N-1)*H), 세로선마다 가로선을 놓을 수 있는 위치의 개수 H (1 ≤ H ≤ 30)
• 출력: 추가해야 하는 가로선 개수의 최솟값 (최대 3개, 초과 시 -1)

문제: https://www.acmicpc.net/problem/15684

풀이: 행(Row) 기준 백트래킹 및 가지치기(Pruning)

2차원 맵의 처음부터 매번 탐색을 진행하면 시간 초과가 발생하므로, 현재 탐색 중인 행 번호를 기록하여 효율적으로 탐색을 이어나가는 방식입니다.

• 가지치기 (Early Exit): 현재 추가한 가로선의 개수(cnt)가 이미 구한 최소 가로선 개수(ans)보다 크거나 같다면, 더 이상 탐색할 가치가 없으므로 즉시 종료(return)하여 연산 시간을 대폭 단축합니다. 최대 개수가 3개이므로 cnt > 3인 경우도 즉시 쳐냅니다.
• 행 기준 탐색: 매개변수로 현재 탐색 중인 행 번호(here)를 넘겨줍니다. 다음 재귀 호출 시에도 here 행부터 탐색을 이어나가도록 하여 중복된 앞부분 탐색을 방지합니다. 가로선의 개수 제한이 3개로 적기 때문에, 열(Column) 번호까지 까다롭게 관리하지 않고 행만 넘겨주어도 제한 시간 내에 충분히 통과할 수 있으며 코드가 매우 간결해집니다.
• 가로선 연속 방지: 문제 조건에서 두 가로선은 서로 접하면 안 됩니다. 따라서 가로선을 놓으려는 위치 (i, j)를 기준으로 map[i][j - 1]과 map[i][j + 1]에 이미 가로선이 없는지 확인한 후(!map[i][j] && !map[i][j - 1] && !map[i][j + 1])에만 배치합니다.

코드

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

public class Main {
    static boolean[][] map;
    static int n, m, h;
    static int ans = 4;

    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());
       h = Integer.parseInt(st.nextToken());

       // 양옆 가로선 검사를 위해 배열 크기를 넉넉하게 잡음
       map = new boolean[h + 1][n + 1];
       while (m-- > 0) {
          st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          map[a][b] = true;
       }

       // 1번 행부터, 가로선 0개 배치된 상태로 시작
       go(1, 0);

       bw.write((ans == 4 ? -1 : ans) + "");
       bw.flush();
    }

    // here: 탐색을 시작할 행 번호, cnt: 현재까지 추가한 가로선 개수
    static void go(int here, int cnt) {
       // 1. 가지치기 (개수가 3 초과이거나 이미 찾은 최솟값 이상인 경우)
       if (cnt > 3 || cnt >= ans)
          return;

       // 2. 조작 성공 여부 확인
       if (check()) {
          ans = cnt;
          return;
       }

       // 3. 행 기준 가로선 배치
       for (int i = here; i <= h; i++) {
          for (int j = 1; j < n; j++) {
             // 자신과 양옆에 가로선이 없을 때만 배치 가능
             if (!map[i][j] && !map[i][j - 1] && !map[i][j + 1]) {
                map[i][j] = true;
                go(i, cnt + 1); // 현재 행(i)부터 다시 탐색을 이어감
                map[i][j] = false; // 원상 복구 (백트래킹)
             }
          }
       }
    }

    // 모든 i번 세로선의 결과가 i번으로 나오는지 시뮬레이션
    static boolean check() {
       for (int i = 1; i <= n; i++) {
          int tmp = i;
          for (int j = 1; j <= h; j++) {
             if (map[j][tmp]) {
                tmp++; // 우측으로 이동
             } else if (tmp > 1 && map[j][tmp - 1]) {
                tmp--; // 좌측으로 이동
             }
          }
          if (tmp != i)
             return false;
       }
       return true;
    }
}

알고리즘 분류

구현 (Implementation), 브루트포스 알고리즘 (Brute Force), 백트래킹 (Backtracking)