[C/C++] 백준 - 15684번 : 사다리 조작

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

문제

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

1번 세로선	2번 세로선

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

 

 

삼성 SCPC 기출 문제이다.

사다리를 이어주는 가로선을 최대 3개까지 놓을 수 있을 때 시작 세로선과 도착 세로선을 같게 만들 수 있는 최소한의 가로선의 개수를 구하는 문제이다.

 

입력으로 주어지는 가로선 외의 가로선을 놓을 수 있는 위치에 가로선을 1개, 2개, 3개씩 놓아보며 백트래킹 기법을 통해 결과조건에 충족하는지 안하는지 확인하면 된다.

 

이 한 문제를 푸는데 2일이나 걸렸다.

처음에는 나와있는 예제로 문제를 이해하다보니 문제의 예제에만 해당될 수 있는 변수를 입력해 계속해서 틀렸고,

이걸 해결하고 나니 시간초과가 계속 떴다. 이 부분은 가로선을 놓을 수 있는 위치를 찾는 함수를 2중 for문을 통해 찾았는데 둘 다 0부터 시작해서 탐색하는 완전탐색으로 했더니 시간초과가 났다. 이 부분을 한 번 가로선을 놓을 수 있는 위치를 찾았으면 그 위치 다음부터 탐색하는 방법으로 바꾸고 맞았습니다.를 받을 수 있었다.

 

정말 큰 게 아닌 작은 실수에 2일이나 걸려 오류를 찾았더니 조금 허무했지만 내 실력이 부족하다는 뜻이므로 뭐,, 열심히 해야겠다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#define swap(type,x,y) do{type t=x; x=y;y=t;} while(0)

using namespace std;
// 백준 - 사다리 (삼성기출)
int N, M, H;
int a, b;
bool line[32][14][14];
int ans = 987654321;
bool flag = false;

// 각각의 시작점에서 출발했을 경우 도착지점이 시작지점과 같은지 확인하는 함수
bool is_Can_Down() {
	for (int i = 1; i <= N; i++) {
		int start = i;
		for (int j = 1; j <= H; j++) {
			// j층에서 오른쪽으로 다리가 있는 경우 건너가야함
			if (line[j][start][start + 1] == true) {
				// 오른쪽으로 넘어가서 start+1
				start += 1;
			}
			// j층에서 왼쪽으로 다리가 있는 경우 건너가야함
			else if (line[j][start][start - 1] == true) {
				start -= 1;
			}
			// 다리가 아무것도 없을 경우, 그냥 바로 한칸 내려가도록
			else 
				continue;
		}
		// 모든 층을 돌고 왔을 때, 시작점과 도착점이 다른 경우 false반환
		if (start != i) 
			return false;
	}
	return true;
}

void func(int count, int depth, int start_y, int start_x) {
	if (depth == count) {
		if (is_Can_Down()) {
			// 다리를 추가하여 원하는 결과조건이 충족되므로 더 이상 프로그램 돌릴 필요 x, flag를 true로 바꿈으로써
			// 불필요한 다른 연산 수행x
			flag = true;
			ans = count;
		}
		return;
	}

	if (start_x >= N) {
		start_y++;
		start_x = 1;
	}

	for (int i = start_y; i <= H; i++) {
		for (int j = 1; j <= N-1; j++) {
			if (!line[i][j][j + 1] && !line[i][j][j - 1] && !line[i][j + 1][j + 2]) {
				line[i][j][j + 1] = true;
				line[i][j + 1][j] = true;
				func(count, depth + 1, i, j + 1);
				if (flag) break;
				line[i][j][j + 1] = false;
				line[i][j + 1][j] = false;
			}
		}
		if (flag) break;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// 세로선 ; N, 가로선 ; M, 세로선 마다 가로선을 놓을 수 있는 위치의 개수 H
	cin >> N >> M >> H;
	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		line[a][b][b+1] = true;
		line[a][b + 1][b] = true;
	}

	// 아무 다리를 놓지 않은 채로 검사했을 때 가능한지, 가능하면 0 출력
	if (is_Can_Down()) {
		cout << 0 << '\n';
		return 0;
	}

	// 추가해야하는 가로선은 최대 3개이므로 그때까지 가능하면 최소개수 출력, for문 다 끝날때까지 최소개수 찾지 못하면 -1출력
	for(int i=1;i<=3;i++) {
		func(i, 0,1,1);
		if (ans == i) {
			cout << ans << '\n';
			return 0;
		}
	}
	cout << -1 << '\n';

	return 0;
}