글 읽기 - [15684 : 사다리조작] 시간초과질문

psh4253 1년 전 0

사다리 놓는 과정을 백트래킹 이용해서 중복을 없애줬고, check함수를 이용해 위치체크를해줬습니다.

하지만 시간초과가 떴고 어느부분에서 이를 없앨수있는지 고수님들의 피드백 부탁드립니다 ㅠㅜ

#include <iostream>
#include <queue>
#include <cstdio>
#include <memory.h>
using namespace std;
int N, M, H;
int res;
int map[30][15];
int dx[] = { 0,0};
int dy[] = {-1,1};

bool check(int line) //라인체크
{
	bool ret = false;
	int temp = line;
	int level = 0;
	while(level<H)
	{
		if (map[level][temp]==map[level][temp+1] && map[level][temp] > 0 && map[level][temp + 1] > 0)
			temp++;
		else if (map[level][temp] == map[level][temp - 1] && map[level][temp] > 0 && map[level][temp - 1] > 0)
			temp--;
		level++;
	}
	if (temp == line)
		ret = true;
	return ret;
}

void set_ladder(int curr, int ladder_cnt, int start,int bridge_num, int before_x, int before_y) // 사다리 설정 
{
	if (curr == ladder_cnt)
	{
		//go();
		int correct = 0;
		for (int i = 0; i < N; i++)
		{
			if(check(i))
				correct++;
		}
		if (correct == N)
		{
			res = min(res, curr);
		}
		return;
	}
	else
	{
		for (int i = start; i < H; i++)
		{
			for (int j = 0; j <= N - 2; j++)
			{
				if (map[i][j] == 0 && map[i][j+1] == 0)
				{
					if (i == before_x)
					{
						if (j < before_y)
							continue;
					}
					map[i][j] = bridge_num;
					map[i][j + 1] = bridge_num;
					set_ladder(curr + 1, ladder_cnt, i, bridge_num+1,i,j);
					map[i][j] = 0;
					map[i][j + 1] = 0;
				}
			}
		}
	}
	
}

int main(void)
{
	res = 987654321;
	scanf("%d %d %d", &N, &M, &H);
	int bridge_num = 1;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		map[a - 1][b] = bridge_num;
		map[a - 1][b - 1] = bridge_num;
		bridge_num++;
	}

	for (int ladder_cnt = 0; ladder_cnt <= 3; ladder_cnt++)
	{
		set_ladder(0,ladder_cnt,0,bridge_num,0,0);
		if (0 <= res&&res <= 3)
			break;

	}
	if (res == 987654321)
		res = -1;
	printf("%d\n", res);
}

jh05013 1년 전 1

check가 비효율적입니다. 사다리를 놓는 동시에 어느 시작점이 어느 끝점으로 가는지를 저장하게 하면 직접 시뮬레이션을 돌리지 않고도 check를 할 수 있습니다.

psh4253 1년 전 0

원인은 단순했습니다..
@jh05013 님 말씀도 맞지만
단순히 한점이라도 제위치를 찾지못하면 리턴을 하는 방법도 있습니다..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ACM-ICPC

[15684 : 사다리조작] 시간초과질문

psh4253 1년 전 0

jh05013 1년 전 1

psh4253 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말