[BOJ] 15684번 : 사다리 조작

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n, m, h;
bool ladders[35][15]; 
vector<pair<int, int>> v; // 사다리를 설치할 수 있는 좌표들의 모음집
int ans = INT_MAX;
bool check() {
	for (int i = 1; i <= n; i++) { // 열
		int cur = i; 
		for (int j = 1; j <= h; j++) { // 행
			if (ladders[j][cur]) cur++;
			else if (ladders[j][cur - 1]) cur--;
		}
		if (cur != i) return false;
	}
	return true;
}

void backTrack(int idx, int k, int cnt) {
	if (k == cnt) {
		if (check()) ans = min(ans, cnt);
		return;
	}
	for (int i = idx; i < v.size(); i++) {
		if (!ladders[v[i].first][v[i].second]) {
			ladders[v[i].first][v[i].second] = true; 
			backTrack(i + 1,k + 1, cnt); 
			ladders[v[i].first][v[i].second] = false; 
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> m >> h; 
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b; 
		ladders[a][b] = true; 
	}
	// 사다리를 설치하는 가능한 경우의 수를 다 저장 
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j < n; j++) {
			if (ladders[i][j] || ladders[i][j + 1] || ladders[i][j - 1]) continue; 
			v.push_back({ i,j });
		}
	}
	for (int i = 0; i <= 3; i++) {
		backTrack(0, 0, i);
		if (ans != INT_MAX) break;
	}
	if (ans == INT_MAX) cout << -1 << '\n';
	else cout << ans;

}

backTracking을 이용하여, 풀었다. backTracking을 이용할 때는 parameter에 idx를 두어, 중복을 최대한 피하려고 노력하였다. (순열이 필요 없기 때문에) 내가 코드를 짜면서 , 생각하지 못했던 것은 , 모든 경우의 수를 vector에 집어넣고, 꺼내 쓰면 된다는 생각이다. 나는 이 생각을 하지 못해, do while next_permutation으로 풀어볼까?라고 생각했지만, vector의 크기와 1을 어떻게 추가해야 할지 고민하며, 코드가 꼬였다. 

 

3. solution 2 :

// Authored by : SciEm
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/74da3b10100849d68340661e3e748159
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

bool ladder[32][12];
int idxs[3];
vector<pair<int, int>> coords;  // 고를 수 있는 가로선만을 저장할 벡터
int n, m, h;

// i번째가 i인지 사다리를 타며 확인
bool check() {
  for (int j = 1; j <= n; j++) {
    int cur = j;
    for (int i = 1; i <= h; i++) {
      if (ladder[i][cur - 1]) cur--;
      else if (ladder[i][cur]) cur++;
    }
    if (cur != j) return false;
  }
  return true;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> h;
  while (m--) {
    int a, b;
    cin >> a >> b;
    ladder[a][b] = true;
  }

  for (int i = 1; i <= h; i++)
    for (int j = 1; j < n; j++) {
      // 인접한 것은 애초에 넣지 않음
      if (ladder[i][j - 1] || ladder[i][j] || ladder[i][j + 1]) continue;
      coords.push_back({i, j});
    }


  if(check()){
    cout << 0;
    return 0;
  }

  int ans = 0x7f7f7f7f;
  int sz = coords.size();
  for(int i = 0; i < sz; i++){
    ladder[coords[i].X][coords[i].Y] = true;
    if(check()) ans = min(ans, 1);
    for(int j = i+1; j < sz; j++){
      ladder[coords[j].X][coords[j].Y] = true;
      if(check()) ans = min(ans, 2);
      for(int k = j+1; k < sz; k++){
        ladder[coords[k].X][coords[k].Y] = true;
        if(check()) ans = min(ans, 3);
        ladder[coords[k].X][coords[k].Y] = false;
      }
      ladder[coords[j].X][coords[j].Y] = false;
    }
    ladder[coords[i].X][coords[i].Y] = false;
  }
  if(ans == 0x7f7f7f7f) ans = -1;
  cout << ans;
}
/*
3중 for문 대신 백트래킹을 써도 됨
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/15684.cpp

basic-algo-lecture/0x0D/solutions/15684.cpp at master · encrypted-def/basic-algo-lecture

나도 이 풀이를 참고하여, 백트래킹으로 갔다. 하지만 ,  이 풀이에서는 삼중 for문을 이용해, 3개의 경우의 수를 커버하고 있다.