[백준] 15684번 사다리 조작

15684번 사다리 조작

---

1. 이해하기

• 사다리에 가로선을 놓아 길을 만들어 자신이 출발한 세로선과 끝난 세로선이 같도록 해야 한다.
• 사다리의 가로선을 모두 놓아보는 완전 탐색 문제.

---

2. 구현하기

• 사다리를 타고 내려가보면서 자신이 출발한 세로선에서 끝나는 경우인지 판단.

  bool is_all_match() {
      for(int i = 0; i < N; i++) {
          int x = 0, y = i;
          while(x < H) {
              int num = map[x][y];
              if(num != 0) {
                  if(y-1 >= 0 and map[x][y-1] == num) {
                      y--;
                  } else if(y+1 < N and map[x][y+1] == num) {
                      y++;
                  }
              }
              x++;
          }
          if(y != i) return false;
      }
      return true;
  }

• 최대 3개까지 가로선을 놓아보며 최소로 놓아도 되는 가로선이 몇개인지 찾는다.

  • 이때, 가로선을 놓아도 되는 위치를 잘 파악해야 한다.

  int solve(int cnt, int r) {
      if(cnt > 3) return MAX;
      if(is_all_match()) return cnt;
  
      int ret = MAX;
      for(int i = r; i < H; i++) {
          for(int j = 0; j < N; j++) {
              if(map[i][j] != 0) continue;
              if(j+1 < N and map[i][j+1] == 0) {
                  map[i][j] = map[i][j+1] = j+1;
                  ret = min(ret,solve(cnt+1,i));
                  map[i][j] = map[i][j+1] = 0;
              }
          }
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
const int MAX = 987654321;
int map[31][10];
int N,M,H;

bool is_all_match() {
    for(int i = 0; i < N; i++) {
        int x = 0, y = i;
        while(x < H) {
            int num = map[x][y];
            if(num != 0) {
                if(y-1 >= 0 and map[x][y-1] == num) {
                    y--;
                } else if(y+1 < N and map[x][y+1] == num) {
                    y++;
                }
            }
            x++;
        }
        if(y != i) return false;
    }
    return true;
}

int solve(int cnt, int r) {
    if(cnt > 3) return MAX;
    if(is_all_match()) return cnt;

    int ret = MAX;
    for(int i = r; i < H; i++) {
        for(int j = 0; j < N; j++) {
            if(map[i][j] != 0) continue;
            if(j+1 < N and map[i][j+1] == 0) {
                map[i][j] = map[i][j+1] = j+1;
                ret = min(ret,solve(cnt+1,i));
                map[i][j] = map[i][j+1] = 0;
            }
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N >> M >> H;
    for(int i = 0; i < M; i++) {
        int h,n;
        cin >> h >> n;
        h--; n--;
        map[h][n] = map[h][n+1] = n+1;
    }

    int ans = solve(0,0);
    if(ans == MAX) cout << -1 << '\n';
    else cout << ans << '\n';
    return 0;
}