문제 링크
https://www.acmicpc.net/problem/15684
15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선
www.acmicpc.net
접근 방법
이 문제는 사다리에 추가적으로 가로선을 0개 부터 최대 3개까지 놓는 가능한 모든 경우의 수를 다 보아야 해결 할 수 있다. 결국 조합 문제로 해석될 수 있으므로, 백트래킹을 하며 모든 조합에 대해 문제의 조건은 1번째부터 i번째에서 출발할 때 순서대로 1번째부터 i번째의 도착 지점에 도달하면 카운트하고, 그 카운트가 4이상이거나 가능한 방법이 없다면 -1을 출력하면 된다.
(1) 변수
map[h][l]는 h의 높이, l번째 라인이 h의 높이, l+1번째 라인에 가로선이 연결되어 있다면 1, 아니면 0으로 나타낸다.
(2) go() 함수
bool go() {
for (int i = 1; i <= N; i++) {
int nowl = i;
for (int nowh = 0; nowh <= H; nowh++){
if (map[nowh][nowl] == 1)
nowl++;
else if (map[nowh][nowl - 1] == 1)
nowl--;
}
if (nowl != i)
return false;
}
return true;
}이 함수는 사다리의 출발지점과 도착지점이 같은지 따라가보는 함수이다.
모든 사다리의 출발지점 1~N에 대해 확인 하여야 하기 때문에 for문에서 경우를 검사해보자. 현재 출발 라인을 nowl = i 라 하고, nowh(0~H)를 따라갈때, 우측에 사다리가 있는 경우 (if(map[nowh][nowl] == 1)) 라인을 오른쪽으로 옮겨갈 것(nowl++)이고, 좌측에 사다리가 있는 경우 (if(map[nowh][nowl - 1] == 1)) 라인을 왼쪽으로 옮겨갈 것(nowl--)이다.
(3) solve()함수
void solve(int cnt, int now_h, int now_l) {
if (go()) {
result = min(cnt, result);
return;
}
if (cnt == 3)
return;
for (int h = now_h; h <= H; h++) {
for (int l = now_l; l < N; l++) {
if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0) {
map[h][l] = 1;
solve(cnt + 1, h, l);
map[h][l] = 0;
}
}
now_l = 1;
}
}이 함수는 조합을 보기 위한 백트래킹(DFS) 함수이다. 중복되는 경우를 보지 않기 위해 매게변수로(nowl, nowh)를 사용하였으며, 위 함수가 호출되는 모든 경우에 대해 위에 설명한 go()함수로 조건을 만족하는지 검사한다. cnt가 3보다 커지는 경우는 고려하지 않으므로 cnt는 3에서 return을 하게 된다.
가로선을 추가 할 수 있는 경우인,
양쪽에 가로라인이 존재하지 않을 때(if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0))
가로라인을 추가(map[h][l] = 1)하고, 함수를 진행 시킨뒤(solve(cnt + 1, h, 1)), 함수가 종료되면 해당 가로라인을 다시 삭제 (map[h][l] = 0)하면 된다.
소스 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, H;
int map[32][12]; //height, line
int result = 4;
bool go() {
for (int i = 1; i <= N; i++) {
int nowl = i;
for (int nowh = 0; nowh <= H; nowh++){
if (map[nowh][nowl] == 1)
nowl++;
else if (map[nowh][nowl - 1] == 1)
nowl--;
}
if (nowl != i)
return false;
}
return true;
}
void solve(int cnt, int now_h, int now_l) {
if (go()) {
result = min(cnt, result);
return;
}
if (cnt == 3)
return;
for (int h = now_h; h <= H; h++) {
for (int l = now_l; l < N; l++) {
if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0) {
map[h][l] = 1;
solve(cnt + 1, h, l);
map[h][l] = 0;
}
}
now_l = 1;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> H;
for (int i = 1; i <= M; i++) {
int a, b;
cin >> a >> b; //a높이 b라인
map[a][b] = 1;
}
solve(0, 1, 1);
if (result >= 4)
cout << -1 << "\n";
else
cout << result << "\n";
}
개발 환경 : VS 2019
질문, 지적 환영입니다.
'알고리즘 > 백준' 카테고리의 다른 글
| [C++] 백준 5373 큐빙 (0) | 2020.05.26 |
|---|---|
| [C++] 백준 13460 구슬 탈출 2 (0) | 2020.05.26 |
| [C++] 백준 14891 톱니바퀴 (0) | 2020.05.25 |
| [C++} 백준 14890 경사로 (0) | 2020.05.25 |
| [C++] 백준 15683 감시 (0) | 2020.05.20 |
