글 읽기 - 15684 사다리 조작 문제가 시간초과가 납니다 ㅠㅠ

gogowjdgo1 5년 전 0

테스트케이스는 모두다 맞아서 제출을 했더니 10%를 못가서 시간초과가 납니다.

제 나름대로 디버깅 해보니 무한루프는 아닌듯하구요 알고리즘 문제인듯 합니다.

인터넷에서 다른사람들의 코드를 적어보니 브루트 포스 알고리즘을 돌리는 과정에서 큰차이가 나더군요

저는 다리의 설치가 가능한 지역의 숫자가 n이면 다리는 총 0개~3개만 지을 수 있으므로

"조합"을 통해서 nC0, nC1, nC2, nC3을 순차적으로 돌면서 다리를 놓을 수 있는

모든 경우의 수를 점검하다 정답이 나오면 다리의 수를 출력하는 방식으로 구현하였습니다.

이때까지는 이런식으로 풀어와도 모든 문제가 다 잘풀렸는데 여기서 막혀버리네요...

어떻게 해결해야할까요??

#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;

int N, M, H;
vector<vector<bool>> bridge;
bool isNeighbour = false;
int min_value = INT_MAX;

class Coord
{
public:
	int x, y;
    
	Coord(int x_, int y_) : x(x_), y(y_)
	{	}

	Coord() : Coord(0, 0)
	{	}
};


void PrintArr(int *arr, int n)
{
	cout << endl;

	for (int i = 0; i < n; i++)
	{
		cout <<" "<< arr[i]<<" ";

	}

	cout << endl;
	cout << endl;
}



//true : 이웃한 다리가 있다 /  false : 이웃한 다리가 없다.
bool IsNeighbour(vector<vector<bool>> *copiedBoard)
{
	//다리내에 이웃한 다리가 있는지 점검한다.

	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < N-1; j++)
		{
			if ((*copiedBoard)[i][j] == true)
			{
				//check left
				if (j-1 >= 0)
				{
					if ((*copiedBoard)[i][j - 1] == true)
						return true;

				}


				//check right
				if (j+1 < N-1)
				{
					if ((*copiedBoard)[i][j + 1] == true)
						return true;
				}
			}
		}
	}
	return false;
}


int Simulation(int start, vector<vector<bool>> *bridge, int H, int N)
{
	int x, y;
	x = start;
	y = 0;

	while (y != H)
	{
		//왼쪽 브릿지 확인

		if (x > 0)
		{
			if ((*bridge)[y][x - 1] == true)
			{
				x--;
				y++;
				continue;
			}
		}

		if (x < N-1)
		{
			if ((*bridge)[y][x] == true)
			{
				x++;
				y++;
				continue;
			}
		}

		y++;

	}

	return x;	//도착 지점 좌표를 반환한다.
}


//emptyBridge 다리를 새로 놓을 수 있는 좌표를 담은 vector
void CombSetBridge(int *arr, int arrSize, int m, int n, int index, vector<Coord> *emptyBridge)
{

	if (min_value == INT_MAX)
	{
		if (arrSize == n)
		{
			//PrintArr(arr, n);

			int tmpX = 0, tmpY = 0;

			vector<vector<bool>> copiedBridge = bridge;

			for (int i = 0; i < n; i++)
			{
				tmpX = (*emptyBridge)[arr[i]].x;
				tmpY = (*emptyBridge)[arr[i]].y;

				copiedBridge[tmpY][tmpX] = true;
			}

			if (IsNeighbour(&copiedBridge))
				return;

			//시뮬레이션시 모든 시작점과 도착점이 같은지 점검한다.
			for (int i = 0; i < N - 1; i++)
			{
				int result = Simulation(i, &copiedBridge, H, N);

				if (i != result)
					return;

			}

			//시뮬레이션 조건이 충족되면 출력을 비교한다.
			if (min_value > n)
			{
				min_value = n;
			}

			return;
		}

		if (index == m)
			return;

		arr[arrSize] = index;
		CombSetBridge(arr, arrSize + 1, m, n, index + 1, emptyBridge);
		CombSetBridge(arr, arrSize, m, n, index + 1, emptyBridge);
	}
}


int main(void)
{

	cin >> N >> M >> H;
	
	bridge.assign(H, vector<bool>(N-1, false));

	int a, b;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;

		bridge[a-1][b-1] = true;
	}

	vector<Coord> emptyBridge;	

	//다리가 없는 지점의 좌표를 emptyBridge에 넣는다.
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < N - 1; j++)
		{
			if (bridge[i][j] == false)
			{
				if (j - 1 >= 0)
				{
					if (bridge[i][j - 1] == true)
						continue;
				}

				if (j + 1 < N - 1)
				{
					if (bridge[i][j + 1] == true)
						continue;
				}

				emptyBridge.push_back(Coord(j,i));
			}
		}
	}

	int *arr=new int[emptyBridge.size()];

	//n = 0~mptyBridge.size() 까지 경우의 수를 모두 확인 한다.
	//CombSetBridge(arr, 0, emptyBridge.size(), 3, 0);

	
	for (int i = 0; i <= 3 && min_value == INT_MAX; i++)
	{
		CombSetBridge(arr, 0, emptyBridge.size(), i, 0, &emptyBridge);
		//cout << i << endl;
	}
	

	//CombSetBridge(arr, 0, emptyBridge.size(), 3, 0, &emptyBridge);

	if (min_value != INT_MAX)
	{
		cout << min_value << endl;
	}
	else
	{
		cout << -1 << endl;
	}

	
	/*
	for (int i = 0; i < M; i++)
	{
		int result = Simulation(i, &bridge, H, N);

		if (i != result)
			return 0;

	}

	cout << "조건 충족" << endl;
	*/


	return 0;
}

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

문제

문제

출처

ICPC

15684 사다리 조작 문제가 시간초과가 납니다 ㅠㅠ

gogowjdgo1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말