백준 알고리즘 15684_사다리 조작 c

문제

(링크)15684번: 사다리 조작 (acmicpc.net)

15684번: 사다리 조작

 

사고과정

문제를 처음 읽었을 때 왜이렇게 정답률이 낮은거지?라고 생각할 만큼 그리 어려운 문제는 아니라고 생각했다. 그러나 시간제한이 2초라고 되어있기 때문에 우리는 시간초과를 유의하여 코드를 짜야한다. 

조건 입력 -> 사다리를 x번(0~3) 추가 -> 사다리를 탐색  -> 반복  --> 종료조건을 만족하면 사다리 최소 추가회수 출력 의 구조를 생각했다. 그러므로 함수는 총 2개 ①사다리 탐색함수와  ②사다리를 추가하는함수가 필요하다. 이후 전역변수 end_flag를 설정하여, 사다리를 3번을 다 추가하기전에 언제든 종료조건이 성립되면 모든 기능을 다운하도록 하였다.

사다리의 구조와 정보를 저장할 배열의 구조도 잘 연관시켜야한다. 나는 다음과 같은 그림을 보며 문제를 풀었다.

 

내코드

#include <stdio.h>
#include <stdlib.h>

#define ABLE 1
#define UNABLE -1
#define EMPTY 0


int col_num, row_num, row_state,end_flag=0;


int playLadder(int** ladder) {
	int ref, tar;
	for (ref = 0; ref < col_num-1; ref++) {		//마지막 줄은 검사 안해도 됨
		tar = ref;
		for (int i = 0; i < row_num; i++) {
			if (ladder[i][tar] == ABLE)tar++;
			else if (tar-1>=0 && ladder[i][tar-1] == ABLE)tar--;
			else continue;
		}

		if (tar != ref)return 0;
	}
	return 1;
}


void addLadder(int add_count, int maxAdd, int** ladder, int start_x, int start_y) {
	if (end_flag)return;
	if (add_count == maxAdd) {
		if (playLadder(ladder)) {
			end_flag=1;
			printf("%d",maxAdd);
		}
		return;
	}

	for (int i = start_y; i < row_num; i++) {	//중복된 조합을 피하기 위함. 
		int j = 0;			
		if (i == start_y)j = start_x;			//같은 행, 같은 열에서부터 탐색, 현재 추가한
		while (j < col_num - 1) {		//사다리의 이전 사다리는 다시 추가할 필요가 없음
			if (ladder[i][j] == EMPTY) {
				int temp = ladder[i][j + 1];
				ladder[i][j] = ABLE;
				ladder[i][j+1] = UNABLE;
				addLadder(add_count + 1, maxAdd, ladder, j, i);
				ladder[i][j] = EMPTY;
				ladder[i][j + 1] = temp;
			}
			j++;
		}
	}



}


int main() {	
	int i, j;
	scanf("%d %d %d", &col_num, &row_state, &row_num);
	int** ladder = (int**)calloc(row_num, sizeof(int*));
	for (i = 0; i < row_num; i++) {
		ladder[i] = (int*)calloc(col_num, sizeof(int));
		ladder[i][col_num - 1] = UNABLE;
	}

	for (i = 0; i < row_state; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		ladder[a - 1][b - 1] = ABLE;
		ladder[a - 1][b] = UNABLE;
		if (b - 2 >= 0)ladder[a - 1][b - 2] = UNABLE;
	}

	
	int maxAdd;
	for (maxAdd = 0; maxAdd <= 3; maxAdd++) {
		if (!end_flag) {
			addLadder(0,maxAdd,ladder,0,0);
		}
		else break;
	}
	if (!end_flag) {
		printf("-1");
	}






	for (i = 0; i < row_num; i++) {
		free(ladder[i]);
	}
	free(ladder);
	return 0;
}

먼저 배열 ladder는 각 사다리의 교차점을 나타낸다. 즉 ladder[0][0]은 첫 세로줄과 첫 가로줄이 만나는 지점이다. 즉 입력으로 들어오는 정보와는 1의 차이가 있다. 입력에서 a는 가로줄 b는 세로줄을 나타내므로 ladder[a-1][b-1] = ABLE이 된다. 즉 해당 지점에서 오른쪽으로 사다리가 놓아져 있다는 것이다. 그런데 문제에서 사다리를 연속해서 놓을 수 없다고 했으므로 ladder[a-1][b-2]와 ladder[a-1][b]는 UNABLE이 된다.(b-2가 배열 범위 내에 있을 때). 그리고 한가지 중요한 점은 맨 오른쪽 사다리는 그 오른쪽으로 사다리를 놓을 수 없으므로 모두 UNABLE이 된다. 

이제 maxAdd의 개수만큼 사다리르 추가해줘야한다. 문제에서 최소개수를 구하라고 했으므로 maxAdd는 0부터 시작하는데 end_flag가 0일 때만 사다리를 추가하고, end_flag가 1이 되면 풀이를 끝낸다. 

playLadder함수는 현재 사다리를 탐색하는 함수이다. 0번 사다리부터 마지막 직전 사다리까지 탐색하는데,( 마지막 사다리는 나머지 사다리의 상태에 따라 결정된다) n번째 사다리의 꼭대기 부터 시작하여 아래로 내려간다. 이때 tar는 해당 n번 사다리에서 시작하여 아래로 내려갈 수록 가로 사다리의 상태에따라 이름이 변한다. ladder[i][tar] 또는 ladder[i][tar-1]이 ABLE이면 오른쪽/왼쪽으로 이동하고 이외엔 생략한다. 마지막에 tar과 n번이 같다면 탐색을 계속하고 한번이라도 다르게 나온다면 0을 return한다.

addLadder함수는 실질적인 재귀함수로, 사다리를 추가하는 경우의 수를 빠짐없이 탐색하는 역할을한다. addLadder의 종료 조건은 ①end_flag가 1 이거나 ②사다리를 추가해준 횟수가 maxAdd와 같아질 때이다. ②조건을 만족하면 playLadder의 반환 값에 따라 maxAdd를 출력한다. 사다리를 추가하는 것은 어렵지 않다. maxAdd만큼 재귀를 반복하게 되는데, 이 때 중요한 것은 중복된 조합을 피하는 것이다. 이는 2중 배열에서 y index와 x index를 함수의 인자로 넣어 간단하게 해결할 수 있다.  

만약 end_flag가 maxAdd가 3을 넘어갈 때까지 1이 안된다면 -1을 출력한다.

 

피드백

처음 코드는 c++을 이용하여 작성했다. vector를 사용하고 싶었기 때문이다. 처음 코드를 짤 때 중복탐색을 피하기 위해 '현재 추가한 사다리' 정보를 다음 탐색에 넘겨가며 코드를 짰고, 사다리 추가가 끝난 뒤 해당 사다리가 종료조건을 만족하는지를 찾을 때도 마지막 사다리는 탐색하지 않고, 앞 번호의 사다리부터 탐색할 때 조건에 맞지 않으면 가차없이 0을 return하여 탐색 시간을 줄이고자 하였다. 그런데도 특정 케이스(9%)에서 시간초과가 떴다. 아직도 이게 왜 안되는지 모르겠다. 너무 답답해서 구글링을 하며 다른 사람들의 코드도 봤는데, 딱히 어떤 것을 더 추가하고 빼야하는지를 모르겠다. 

그래서 아무생각없이 처음부터 차근차근 c를 이용하여 코드를 짰더니........통과했다.......... 진짜 할 말이 없어졌다. 코드 구조와 내용은 거의 똑같은데, 왜 vector를 이용할 때에 비해 이중 배열을 이용할 때 '시간 제한'에 걸리지 않을만큼 시간이 단축되는걸까.

아래는 시간초과가 된 코드

#include <iostream>
#include <vector>

#define UNABLE -1
#define ABLE 1
#define NONE 0

using namespace std;

int col, row, row_position, end_flag = 0;


int FitEndCondition(vector<vector<int>> ladder) {
	int ref, tar;
	for (ref = 0; ref < col - 1; ref++) {
		tar = ref;
		for (int i = 0; i < row_position; i++) {
			if (ladder[i][tar] == ABLE) {
				tar += 1;
			}
			else if (tar > 0 && ladder[i][tar - 1] == ABLE) {
				tar -= 1;
			}
			else continue;
		}

		if (tar != ref) {
			return 0;		//같지 않은게 있으면 return 0
		}
	}
	return 1;  //모두 자기 번호대로 가면 return 1
}

void addLadder(int add_count, int maxAdd, vector<vector<int>> ladder, int start_x, int start_y) {
	if (end_flag)return;
	if (add_count == maxAdd) {
		if (FitEndCondition(ladder)) {
			end_flag = 1;
			cout << maxAdd;
		}
		return;
	}



	for (int i = start_y; i < row_position; i++) {
		int j = 0;
		if (i == start_y)j = start_x;
		while (j < col) {
			if (ladder[i][j] == NONE) {
				int tmp = ladder[i][j + 1];
				ladder[i][j] = ABLE;
				ladder[i][j + 1] = UNABLE;
				//cout << i << ' ' << j << endl;
				addLadder(add_count + 1, maxAdd, ladder, j, i);
				ladder[i][j] = NONE;
				ladder[i][j + 1] = tmp;
				if (end_flag)return;
			}
			j++;
		}
	}
}


int main() {
	cin >> col >> row >> row_position;
	vector<vector<int>> ladder(row_position, vector<int>(col, NONE));
	for (int i = 0; i < row_position; i++) {
		ladder[i][col - 1] = UNABLE;
	}
	for (int i = 0; i < row; i++) {
		int a, b;
		cin >> a >> b;
		ladder[a - 1][b - 1] = ABLE;
		if (b - 2 >= 0)ladder[a - 1][b - 2] = UNABLE;
		if (b < col)ladder[a - 1][b] = UNABLE;
	}


	int maxAdd = 0;
	while (maxAdd <= 3) {

		addLadder(0, maxAdd, ladder, 0, 0);

		if (end_flag) {
			break;
		}
		maxAdd++;
	}
	if (maxAdd > 3) {
		cout << -1;
	}

	return 0;
}