https://www.acmicpc.net/problem/15684
유형: 시뮬레이션
- 재귀를 이용하여 막대기의 조합 만들기. (선택,비선택)
- check함수를 만들어 col이 원 위치로 오는지 확인
/*
1. 막대기를 먼저 다 놓는다.
2. 제자리로 오는지 확인한다.
main
입력
sol
if index==4 || pos가 끝자리인 경우
if check
끝
r,c 구하기
if map[r][c] ==0 && map[r][c+1]==0
막대기 놓기 가능
map[r][c]=left
map[r][c+1]=right
sol (index+1, pos+1)
다시 0으로 초기화
sol(index,pos+1)
check
for c
for r
map이 right면 c을 하나 증가
map이 left면 c을 하나 빼기
if pos하고 c하고 틀리면 return
*/
#include<iostream>
#include<algorithm>
using namespace std;
int LEFT = 1;
int RIGHT = 2;
int N, M, H;
int map[30][10] = { 0, };
int ans=300;
bool check() {
for (int c = 0; c < N; c++)
{
int pos = c;
for (int r = 0; r < H ; r++) {
if (map[r][pos] == RIGHT) {
pos++;
}
else if (map[r][pos] == LEFT) {
pos--;
}
}
if (pos != c) return false;
}
return true;
}
void sol(int index,int pos) {
if (index == 3 || pos > H * N) {
if (check()) {
ans = min(ans, index);
}
return;
}
int row = pos / N;
int col = pos % N;
if (col+1<N && map[row][col] == 0 && map[row][col+1] == 0) {
map[row][col] = RIGHT;
map[row][col + 1] = LEFT;
sol(index + 1, pos+2);
map[row][col] = 0;
map[row][col + 1] = 0;
}
sol(index, pos + 1);
}
int main() {
cin >> N >> M >> H;
for (int i = 0; i < M; i++) {
int y, x;
cin >> y >> x;
--y; --x;
map[y][x] = RIGHT;
map[y][x + 1] = LEFT;
}
sol(0,0);
if (ans == 300)
{
cout << -1;
}
else
{
cout << ans;
}
}
'알고리즘 > 백준' 카테고리의 다른 글
백준 16234 인구 이동 (0) | 2020.03.13 |
---|---|
백준 15686 치킨 배달 (0) | 2020.03.13 |
백준 15685 드래곤 커브 (0) | 2020.03.13 |
15683 감시 (0) | 2020.03.12 |
14891번 톱니바퀴 (0) | 2020.03.12 |