https://www.acmicpc.net/problem/15684
15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선
www.acmicpc.net
풀이
문제의 입력을 보면 세로선의 개수는 최대 10개, 높이는 최대 30개이다. 즉 놓치 못하는 규칙을 고려하지 않았을 때 가로선이 있을 수 있는 위치는 총 300개이다. 또 최대 3개의 가로선을 추가할 수 있는 조건을 보았을 때 브루트 포스 알고리즘으로 백트래킹을 사용해도 풀릴 수 있는 문제라고 생각하였다. 따라서 가로선이 놓일 수 있는 부분이 겹치지 않게 놓다보면 시간초과가 발생하지 않을 것이다.
가로선은 세로선에서 오른쪽으로만 놓는다고 생각한다. 따라서 j번 세로선에 놓는다고 했을 때 j-1, j+1의 세로선에 모두 가로선이 존재하지 않아야한다. 만약 j번에 놓을 수 있을 때 dfs를 이용하여 재귀적으로 j번 세로줄부터 놓을 수 있는 위치를 다시 계산한다. 최대한 중복을 줄이기 위해 j번 세로줄부터 확인하는 것이다.
소스 코드
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
const int MN = 9;
int N, M, H;
int ans = 4; //최대 3까지이므로 4로 설정
void dfs(int now, int n, bool ladder[31][11]) {
if(n >= ans) return; //이미 최소값을 넘은 경우 탐색하지 않음
bool chk = false; //모두 j번 세로줄이 j번에서 끝나는지 확인하는 변수
for(int j = 1; j <= N; j++) {
int now = j;
for(int i = 1; i <= H; i++) {
if(ladder[i][now-1]) { //왼쪽에 길이 있다면 왼쪽 세로줄로 이동
now--;
}
else if(ladder[i][now]) { //오른쪽에 길이 있다면 오른쪽 세로줄로 이동
now++;
}
}
if(now != j) { //만약 j번에서 끝나지 않은 경우
chk = true; //끝나지 않음을 체크 후 종료
break;
}
}
if(!chk) { //만약 모두 알맞게 끝난 경우
ans = min(ans, n); //최소값 갱신 후 더 이상 탐색하지 않음
return;
}
if(n == 3) return; //3개 가로줄 사용한 경우 리턴
for(int j = now; j < N; j++) { //지금까지 탐색한 세로줄부터
for(int i = 1; i <= H; i++) { //모든 높이를 탐색
if(!ladder[i][j] && !ladder[i][j+1] && !ladder[i][j-1]) { //가로줄을 놓을 수 있는 경우
ladder[i][j] = true; //가로줄 생성
dfs(j, n+1, ladder); //재귀
ladder[i][j] = false; //가로줄 제거
}
}
}
}
int main() {
cin >> N >> M >> H;
bool ladder[31][11];
memset(ladder, 0, sizeof(ladder)); //사다리 초기화
for(int i = 0; i < M; i++) {
int a, b; cin >> a >> b;
ladder[a][b] = true; //가로줄 추가
}
dfs(1, 0, ladder); //재귀로 탐색
if(ans == 4) cout << -1; //방법이 없는 경우 -1출력
else cout << ans;
}위 과정대로 작성한 코드이다. 방법이 없는 경우를 고려해 초기값을 4로 설정했다. 최대 3까지 정답이 될 수 있기 때문이다.
채점 결과
'알고리즘 > 백준' 카테고리의 다른 글
| [C++] 백준 14891번 톱니바퀴 풀이 (0) | 2021.08.26 |
|---|---|
| [C++] 백준 14500번 테트로미노 풀이 (0) | 2021.08.25 |
| [C++] 백준 12865번 평범한 배낭 풀이 (0) | 2021.08.24 |
| [C++] 백준 1958번 LCS 3 풀이 (0) | 2021.08.24 |
| [C++] 백준 5502번 펠린드롬 풀이 (0) | 2021.08.24 |
