[BOJ15684] 사다리 조작

[BOJ15684] 사다리 조작

문제 링크

문제 설명

• 2018 삼성 상반기 기출문제.

코드 리뷰

• 세시간 오바…
• 처음 접하는 문제유형 느낌이라 어떻게 풀지 고민하는데 시간을 많이 썼다.
• 결국 사다리를 1개, 2개, 3개를 선택하여 설치하는 조합의 경우의 수가 완탐으로 해결할 수 있는 시간이라는 결론을 내렸고, 가지를 쳐서 해결하였다.
• 문제 푸는 과정에서 배열 값이 0일 땐 아래로 내려가고, 1일 땐 좌 우가 1인 곳으로 이동하게 풀었는데, 현재 출발할 곳이 1이고 도착지점이 1이라고 해도 연결되있지 않은 경우를 생각을 못해서 그 부분에서 디버깅하는데 시간이 오래 걸렸다.
• 사다리를 추가할 때, 배열을 num과 char dir 변수를 가지고 있는 구조체로 선언하여, 사다리가 왼쪽으로 뻗어나가는 경우는 L을, 오른쪽으로 뻗어나가는 부분은 R을 입력하여 정보를 확인하였다.
• 가지를 치고나니 시간이 확연하게 줄어든 코드를 만들었다.
• 다음에 풀 땐 조금 더 깔끔한 코드를 구현해보겠다.

#include <iostream>
using namespace std;

typedef struct {
	int num;
	char dir;
}Board;

int N, M, H;
Board board[35][12];
int ans = 100000;

int checkladder() {
	for (int n = 1; n <= N; n++) {
		int nnow = n;
		int hnow = 1;
		while (hnow <= H + 1) {
			if (board[hnow][nnow].num == 0) hnow++;
			else if (board[hnow][nnow].num == 1) {
				if (board[hnow][nnow].dir == 'r') {
					nnow++;
				}
				else nnow--;
				hnow++;
			}
		}
		if (nnow != n) return 0;
	}
	return 1;
}

void dfs(int n, int m, int cnt) {
	if (cnt >= ans) return;
	if (n > N || m > H) return;
	if (checkladder()) ans = cnt;
	if (cnt == 3) return;
	for (int nnow = n; nnow < N; nnow++) {
		for (int hnow = 0; hnow <= H; hnow++) {
			if (board[hnow][nnow].num == 1) continue;
			if (nnow + 1 <= N && board[hnow][nnow + 1].num == 0) {
				board[hnow][nnow].num = 1;
				board[hnow][nnow].dir = 'r';
				board[hnow][nnow+1].num = 1;
				board[hnow][nnow+1].dir = 'l';
				dfs(nnow, hnow, cnt + 1);
				board[hnow][nnow + 1].num = 0;
				board[hnow][nnow].num = 0;
			}
		}
	}

}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M >> H;
	if (M == 0) {
		cout << "0\n";
		return 0;
	}
	for (int m = 0; m < M; m++) {
		int a, b;
		cin >> a >> b;
		board[a][b].num = 1;
		board[a][b].dir = 'r';
		board[a][b + 1].num = 1;
		board[a][b + 1].dir = 'l';
	}
	dfs(1, 1, 0);
	if (ans == 100000) ans = -1;
	cout << ans << '\n';
	return 0;
}