글 읽기 - 시간초과가 나오네요...dfs를 통해 조합으로 풀었습니다..

leekang9070 4년 전 0

완전 탐색을 통해 문제를 해결 하였습니다. 그렇지만 시간 초과가 뜨내요.. 나름대로 가지치기도 잘 했고

조합을 통해서 중복을 최소화 했다고 생각되는데.. 고수님들 도움 부탁드립니다.. ㅠㅠ

#include<iostream>
using namespace std; 
bool arr[500][500][500];
int ysize; 
int xsize; 
int h;
class Point {
public: 
	int start; 
	int end;
	int floor; 
};
 
Point point[500000];
int pointsize = 0; 
int zz = 1; 

bool finish()
{
	for (int i = 0; i < xsize; i++)
	{
		int gx = i; 
		int gf = 0; 
		for (int j = 0; j < ysize; j++)
		{
			if (gx - 1 >= 0 && arr[gx][gx-1][gf]==1)
			{
				gx = gx - 1;
				gf++;
			}
			else if (gx + 1 < xsize && arr[gx][gx + 1][gf] == 1)
			{
				gx = gx + 1;
				gf++;
			}
			else
			{
				gf++;
			}
		}

		if (gx != i)
		{
			return false;
		}
	}
	return true;
}

void push()
{
	for (int i = 0; i < xsize-1; i++)
	{
		for (int j = 0; j < ysize; j++)
		{
			Point a; 
			a.start = i;
			a.end = i + 1;
			a.floor = j;
			point[pointsize] = a;
			pointsize++;
		}
	}
}

int result= 1874919423;

void dfs(int count, int index)
{
	if (count > 3 || count >= result || index >=pointsize)
	{
		return;
	}
	if (finish() == true)
	{
		if (count < result)
		{
			result = count;
		}
	}

	for (int i = index; i < pointsize; i++)
	{
		int start = point[i].start;
		int end = point[i].end;
		int floor = point[i].floor;

		
		if (arr[start][end][floor] == false)
		{
			int check = 0;
			if (start - 1 >= 0)
			{
				if (arr[start - 1][start][floor] == 1)
				{
					check = 1;
				}
			}

			if (end + 1 < ysize)
			{
				if (arr[end][end + 1][floor] == 1)
				{
					check = 1;
				}
			}
			if (check == 0)
			{
				arr[start][end][floor] = true;
				arr[end][start][floor] = true;
				dfs(count + 1, i + 1);
				arr[start][end][floor] = false;
				arr[end][start][floor] = false;
			}
			dfs(count, i + 1);
		}

		
	}

}

int main() {
	int add; 
	cin >> xsize >> add >> ysize; 
	for (int i = 0; i < add; i++)
	{
		int start; 
		int end; 
		int floor; 
		cin >> floor >> start; 
		start--;
		floor--;

		end = start + 1;
		arr[start][end][floor] = true;
		arr[end][start][floor] = true;
	}

	push();
	dfs(0, 0);
	if (result > 3)
	{
		cout << -1 << endl;
		return 0; 
	}
	cout << result << endl;
}

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

문제

문제

출처

ICPC

시간초과가 나오네요...dfs를 통해 조합으로 풀었습니다..

leekang9070 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말