이번 문제는 백준의 골드 3 문제 사다리 조작 문제이다.
문제를 차근 차근 한 번 읽어보자.
간단한 사다리 게임에 대한 문제이다.
i번에서 사다리를 타고 내려가면, 반드시 i에 도착해야 한다.
세로선 수와 가로선 수가 주어지고, 이미 놓아진 가로선이 주어진다.
이 때 최소로 가로선을 추가하여 모든 i와 i가 연결되도록 하자!
굉장히 특이한 문제인거 같은데, 문제를 어떻게 풀어야 할까?
완전탐색
세로선은 총 10개, 가로선은 총 30개가 주어질 수 있다.
만약 모든 위치에 가로선을 놓아보며 직접 내려보내 본다면?
가로선이 놓일 수 있는 위치는 총 300개이다.
또한, 3개 이상 가로선을 놓는 경우는 생각하지 않아도 된다.
그럼 300개의 자리 중 1, 2, 3개를 선택하는 것과 같다.
300자리 중 1자리를 선택하는 것은 300C1이다.
300자리 중 2자리를 선택하는 것은 300C2이다.
300자리 중 3자리를 선택하는 것은 300C3이 된다.
즉, 최악의 경우 300C1 + 300C2 + 300C3이 되는 것이다.
생각보다 시간이 얼마 걸리지 않을 것 같다.
완전탐색으로 한 번 조합을 구현해보자!
어떻게 하면 가로선을 놓을 자리를 정할 수 있을까?
ladder_map[x][y]라는 사다리를 표현할 배열을 하나 생성하자.
y 가로선에서 x와 x + 1을 잇는다는 의미의 배열이 된다.
이제 세로선을 기준으로 이중 for문을 돌리면 될 것 같다.
세로선을 1번부터 훑으며, 안에서 가로선을 1번부터 다시 놓아보는 것이다.
아래와 같이 구현해 보았다.
void backtrack(int idx, int depth) {
if (depth == 4)
return;
if (check_ladder()) {
answer = min(answer, depth);
return;
}
for (int i = idx; i < vert; i++) {
// 어차피 마지막 세로선은 사다리를 설치할 수 없다.
// ㅣ->ㅣ 방향으로 밖에 설치 못함
for (int j = 1; j <= hori; j++) {
if (ladder_map[j][i])
continue; // 이미 선이 놓인 곳
if (ladder_map[j][i - 1] || ladder_map[j][i - 1])
continue; // 선은 연속할 수 없다.
ladder_map[j][i] = true;
backtrack(i, depth + 1);
ladder_map[j][i] = false;
}
}
}매번 가로선을 놓을 때 마다 check_ladder() 함수로 검사해야 한다.
1개, 2개, 3개 모든 경우에서의 가능성을 봐야하기 때문이다.
최종적으로 아래와 같이 구현되었다.
int vert = 0, hori = 0, put_point = 0, x = 0, y = 0, answer = MAX;
bool ladder_map[31][11];
void optimize() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
}
bool check_ladder() {
for (int i = 1; i <= vert; i++) {
// i는 현재 내려보내는 번호
int curr_vert = i;
for (int j = 1; j <= hori; j++) {
if (ladder_map[j][curr_vert])
curr_vert++; // 내려가다 가로선을 만나는 경우
else if (ladder_map[j][curr_vert - 1])
curr_vert--; // 내려가다 가로선을 만나는 경우
// 반대로 가는 선은 현재 (세로선 - 1)의 값을 가진다.
}
if (curr_vert != i)
return false;
}
return true;
}
void backtrack(int idx, int depth) {
if (depth == 4)
return;
if (check_ladder()) {
answer = min(answer, depth);
return;
}
for (int i = idx; i < vert; i++) {
// 어차피 마지막 세로선은 사다리를 설치할 수 없다.
// ㅣ->ㅣ 방향으로 밖에 설치 못함
for (int j = 1; j <= hori; j++) {
if (ladder_map[j][i])
continue; // 이미 선이 놓인 곳
if (ladder_map[j][i - 1] || ladder_map[j][i - 1])
continue; // 선은 연속할 수 없다.
ladder_map[j][i] = true;
backtrack(i, depth + 1);
ladder_map[j][i] = false;
}
}
}
int main() {
optimize();
cin >> vert >> put_point >> hori;
for (int i = 0; i < put_point; i++) {
cin >> x >> y;
ladder_map[x][y] = true;
// x번 가로선에서 y와 y + 1을 연결했다는 의미이다.
}
if (put_point == 0)
cout << 0;
else {
// 로직 구현
backtrack(0, 0);
if (answer == MAX)
cout << -1;
else
cout << answer;
}
return 0;
}다행히 정답을 받을 수 있었다!
꽤 까다로운 구현 문제였다고 생각한다.
고민하고 푸는 데에 꽤 시간이 걸렸다.
좀 더 연습해서 구현 문제를 빨리 해결할 수 있도록 해보자!