이번에는 백준 15684번 사다리 조작 문제를 풀어보았습니다.
문제를 처음 봤을 때 가로선을 추가하는 모든 경우를 탐색해야 하기 때문에 백트래킹을 이용하면 해결할 수 있다고 생각했습니다.
가로선을 하나 추가할 때마다 현재 사다리가 조건을 만족하는지 확인하고, 조건을 만족하지 않는 경우에는 다시 다른 위치에 가로선을 추가하는 방식으로 구현하였습니다.
또한 문제에서 최대 3개의 가로선만 추가할 수 있기 때문에 3개를 초과하는 경우는 더 이상 탐색하지 않도록 가지치기를 하였습니다.
문제 설명
사다리 게임에서 가로선을 추가하여 모든 세로선이 자기 자신의 번호로 도착하도록 만들어야 합니다.
추가할 수 있는 가로선은 최대 3개이며, 인접한 가로선은 놓을 수 없습니다.
조건을 만족하기 위해 필요한 최소 가로선 개수를 구하는 문제입니다.
풀이 아이디어
백트래킹을 이용하여 가능한 위치에 가로선을 하나씩 추가하였습니다.
가로선을 추가할 때마다 현재 사다리가 조건을 만족하는지 검사하였습니다.
조건을 만족하면 현재 추가한 가로선 개수와 최솟값을 비교하여 갱신하였습니다.
조건을 만족하지 않는 경우에는 다른 위치에 가로선을 추가하며 계속 탐색하였습니다.
또한 이미 최솟값보다 많은 가로선을 사용한 경우와 3개를 초과한 경우에는 더 이상 탐색하지 않도록 가지치기를 수행하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N, H, M;
int visited[31][11];
int ret = INT_MAX;
bool check() {
for (int i=1; i<N; i++) {
int start = i;
for (int j=1; j<=H; j++) {
if (visited[j][start]) start++;
else if (visited[j][start-1]) start--;
}
if (start != i)
return false;
}
return true;
}
void solve(int here, int cnt) {
if (cnt > 3 || cnt >= ret)
return;
if (check()) {
ret = min(ret, cnt);
return;
}
for (int i=here; i<=H; i++) {
for (int j=1; j<N; j++) {
if (visited[i][j] || visited[i][j-1] || visited[i][j+1]) continue;
visited[i][j] = 1;
solve(i, cnt + 1);
visited[i][j] = 0;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> H;
for (int i=0; i<M; i++) {
int y,x;
cin >> y >> x;
visited[y][x] = 1;
}
solve(1, 0);
if (ret == INT_MAX)
cout << -1 << '\n';
else
cout << ret << '\n';
return 0;
}풀이 흐름
- 기존 가로선을 입력받아 저장합니다.
- 백트래킹을 이용하여 가로선을 하나씩 추가합니다.
- 현재 사다리가 조건을 만족하는지 확인합니다.
- 만족하는 경우 최솟값을 갱신합니다.
- 만족하지 않는 경우 다른 위치에 가로선을 추가하며 계속 탐색합니다.
- 가로선을 3개보다 많이 사용하거나 현재 최솟값 이상이 되면 탐색을 종료합니다.
- 모든 탐색이 끝난 뒤 결과를 출력합니다.
구현 포인트
1. 사다리 결과 확인
현재 사다리 상태에서 모든 세로선이 자기 자신으로 도착하는지 확인하였습니다.
bool check()각 세로선마다 아래로 이동하면서 현재 위치를 계산하였습니다.
if (visited[j][start]) start++;
else if (visited[j][start-1]) start--;끝까지 내려간 뒤 시작 위치와 도착 위치가 다르면 false를 반환하였습니다.
2. 백트래킹을 이용한 가로선 추가
가로선을 하나 추가한 뒤 다시 탐색하도록 구현하였습니다.
visited[i][j] = 1;
solve(i, cnt + 1);
visited[i][j] = 0;탐색이 끝난 뒤에는 원래 상태로 복구하였습니다.
3. 가로선을 놓을 수 있는 위치 확인
현재 위치와 양옆에 가로선이 있으면 새로운 가로선을 놓을 수 없습니다.
if (visited[i][j] || visited[i][j-1] || visited[i][j+1]) continue;문제의 조건을 만족하는 위치에서만 가로선을 추가하였습니다.
4. 가지치기
불필요한 탐색을 줄이기 위해 두 가지 경우를 먼저 종료하였습니다.
if (cnt > 3 || cnt >= ret)
return;- 이미 가로선을 3개 초과한 경우
- 현재까지 구한 최솟값보다 많이 추가한 경우
더 이상 탐색할 필요가 없기 때문에 바로 종료하였습니다.
5. 최솟값 갱신
현재 사다리가 조건을 만족하면 최솟값을 갱신하였습니다.
if (check()) {
ret = min(ret, cnt);
return;
}현재 추가한 가로선 개수가 정답 후보가 됩니다.
6. 정답 출력
모든 탐색이 끝난 뒤에도 정답을 찾지 못한 경우에는 -1을 출력하였습니다.
if (ret == INT_MAX)
cout << -1 << '\n';
else
cout << ret << '\n';그렇지 않은 경우에는 최소 추가 개수를 출력하였습니다.
