글 읽기 - 시간 초과 질문드립니다.

alnimee 3년 전 0

아래 소스로 실행시 시간초과 발생하는데 어느 부분에서 제한인 1초가 넘는지 한 번만 봐주시면 감사하겠습니다.

그리고 가능하시다면 어느 부분을 수정 했을 때 (가지치기 추가) 통과할 수 있는지 한 번 분석 부탁드립니다~~

#include <iostream>

#include <stdint.h>
#define endl "\n"
using namespace std;

int testCase, n;
int homeY, homeX, partyY, partyX;
bool possible;
int walking[105];
bool checked[105];

struct Node {
	int x, y;
} convenience[105];

void Init() {
	cin >> n;
	possible = false;
	
	cin >> homeX >> homeY;
	for (int i = 1; i <= n; i++) {
		int tempX, tempY;
		cin >> tempX >> tempY;
		convenience[i] = { tempX, tempY };
	}
	cin >> partyX >> partyY;

	for (int i = 1; i <= n; i++) {
		walking[i] = 0;
		checked[i] = false;
	}
}

int Abs(int num) {
	return num < 0 ? -1 * num : num;
}

bool CheckDistance(int startX, int startY, int endX, int endY) {
	int tempNum = Abs(startX - endX) + Abs(startY - endY);
	if (tempNum <= 1000) return true;
	else return false;
}

bool WalkingToParty() { // 각 부분집합에서 결과가 True 라면 true 반환
	int startX = homeX, startY = homeY;
	int endX = partyX, endY = partyY;

	for (int i = 1; walking[i]; i++) {
		int subX = convenience[walking[i]].x;
		int subY = convenience[walking[i]].y;

		if (CheckDistance(startX, startY, subX, subY)) {
			startX = subX, startY = subY;
		}
		else return false;
	}

	if (CheckDistance(startX, startY, endX, endY)) return true;
	else return false;
}

void DFS(int step) {
	if (step > n || possible) {
		return;
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (checked[i]) continue;
			checked[i] = true;
			walking[step] = i;

			if (WalkingToParty()) {
				possible = true;
				return;
			}

			DFS(step + 1);
			walking[step] = 0;
			checked[i] = false;
		}
	}
}

bool Solve() {
	if (CheckDistance(homeX, homeY, partyX, partyY)) return true;		
	else {
		DFS(1);
		if (possible) return true;
		else return false;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
//	freopen("Input.txt", "r", stdin);

	cin >> testCase;
	for (int t = 1; t <= testCase; t++) {
		Init();
		if (Solve()) cout << "happy" << endl;
		else cout << "sad" << endl;
	}

	return 0;
}

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

문제

문제

출처

ICPC

시간 초과 질문드립니다.

alnimee 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말