[BOJ] 사다리조작

 

1) 시간 초과를 조심 해야 한다. 

 

2) 이건 개인적으로 유용해서 '질문 검색'에서 가져왔다. 

 

james_kylee   3일 전    

테스트케이스가 대략적으로 몇개 나올지 생각해보면 됩니다.

대개 1초에 1억번 연산을 수행한다고 가정하는데, 경우의 수가 천만대 이하면 완전탐색을 하더라도 시간초과를 피할 수 있습니다.

반대로 1억개 이상의 경우의 수를 가진다면 완전탐색으로는 풀 수 없는 문제입니다. 이 경우에는 좀 더 최적화된 알고리즘이 필요합니다.

이 문제의 경우 사다리 수가 (대략적으로) 30 * 10 = 300개이며 1개, 2개, 3개를 선택하는 경우의 수는 300 + 300 * 299 / 2 + 300 * 299 * 298 / 6 < 5000000입니다.

500만개 이하의 경우의 수가 생기는데 이 정도면 충분히 시간 내에 계산할 수 있습니다.

 

3) 예전에 풀다가 시간 초과로 풀지 못했던 문제인데 백트래킹에 유의해야 한다. 먼저 추가될 가로선의 최소값을 ans라고 했을 때

초기값을 4로 놓는다. (가로선은 최대 3개까지 추가될 수 있다.)

 

종료조건 1.

dfs의 파라미터로 넘어오는 cnt(추가된 가로선의 개수 ) 가 ans보다 커버리면 이 함수를 실행시키는 의미가 없기 때문에 리턴한다. 

 

종료조건2. 

i번째 세로선이 i번을 알맞게 찾아갈 때. check라는 함수에서 bool 리턴값을 받아서 true이면 ans값을 갱신하고 리턴한다. 

 

종료조건3. 

cnt == 3일 때 

 

4) 세로선을 추가한다. 

백트래킹을 통해 추가하고 다시 없애주어야 한다. 

이때 유의해야 할 점은 현재 내가 가로선을 생성하려는 위치에 가로선이 없더라도 그 전과 그 후를 살펴봐야 한다. 

lad[col][row] 이 지금 내가 생성하려는 위치일 때 

lad[col][row-1]

lad[col][row+1] 도 살펴봐야 한다. (1이면 이미 가로선이 있는 것!)

 

사다리게임은 가로선이 연속되지 않기 때문이다.

 

5) check() 

row=  i로 고정하고 h만큼 내려가면서 만약 lad[col][row-1] : row-1 과 row 가 연결되어있음 -> row--

lad[col][row] : row 과 row+1 가 연결되어있음 -> row++

 

h만큼 반복했을 때 (사다리를 모두 탐 ) row!=i라면 더 살펴볼 필요 없이 함수를 빠져나온다. 

 

#include <iostream> #include <vector> using namespace std; int n, m, h; bool lad[31][11]; int ans = 4; bool check() { //각자 제자리 찾아가는지 확인하는 역할 for (int i = 1; i <= n; i++) { int row = i, col = 1; while(col <= h) { if (lad[col][row]) { //오른쪽으로 연결되어있다. row++; col++; } else if (lad[col][row-1]) { //왼쪽으로 연결되어있다. row--; col++; } else { col++; } } if (row != i) return false; } return true; } void dfs(int cnt, int col, int row) { //사다리 추가하는역할 if (ans <= cnt) return; if (check()) { ans = cnt; return; } if (cnt == 3) return; for (int i = col; i <= h; i++) { //사다리가 연결된 것을 보고 추가한다. //가로선이 연속되지 않게 추가해줘야 한다. for (int j = row; j < n; j++) { if (!lad[i][j] && !lad[i][j-1] && !lad[i][j+1]) { lad[i][j] = 1; dfs(cnt+1, i, j+1); lad[i][j] = 0; } } row = 1; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> h; if (!m) { cout << 0 << '\n'; return 0; } for (int i = 0; i < m; i++) { int a,b; cin >> a >> b; lad[a][b] = 1; } dfs(0, 1, 1); if (ans == 4) cout << -1 << '\n'; else cout << ans << '\n'; return 0; }