글 읽기 - 시간복잡도에 관해 질문이 있습니다.

hyun353 5년 전 0

15686 치킨배달 문제에서 DFS를 이용한 완전탐색에 관한 시간복잡도 질문이 있어 연락드렸습니다.

현재 아래 코드에서 47~61번 줄에 관한 질문입니다.

처음에 55~61번줄 같이 for문 시작을 0에서 부터 시작하도록 설계 하였습니다. 하지만 이와 같이 설계를 하니 시간초과가 나타났습니다.

그 후 47~53번줄과 같이 for문 시작을 start라는 변수를 통해 시작하도록 하니 시간초과가 나타나지 않았습니다.

혼자 그 이유를 추측해보았는데 for문 시작을 0에서 부터 시작하게되면 최악의 경우 O(13^13)과 같은 시간복잡도가 나오는것 같다 추측하였습니다.

그렇다면 47~53번줄과 같이 코딩하였다면 어느정도의 시간복잡도가 나오는지 추측이 되질 않습니다.

답변해주시면 감사하겠습니다.

// 14:55 ~ 16:06

#include<iostream>
#include<vector>
using namespace std;

struct Point {
	int x;
	int y;
};

int N, M;
int tmin;
vector<Point> chickenRes;
vector<Point> home;

int minDistance[13];
int visited[13];

int cal() {
	int distance = 0;
	for (int i = 0; i < home.size(); i++) {
		int minDis = 2 * N;
		for (int j = 0; j < 13; j++) {
			if (visited[j] == 1) {
				int dis = abs(home[i].x - chickenRes[j].x) + abs(home[i].y - chickenRes[j].y);
				if (minDis > dis)
					minDis = dis;
			}
		}
		distance += minDis;
	}

	return distance;

}

void solution(int m, int start) {
	if (M == m) {
		int result = cal();
		if (tmin > result)
			tmin = result;

		return;
	}

	for (int i = start; i < chickenRes.size(); i++) {
		if (visited[i] != 1) {
			visited[i] = 1;
			solution(m + 1, i + 1);
			visited[i] = 0;
		}
	}

//    for (int i = 0; i < chickenRes.size(); i++) {
//		if (visited[i] != 1) {
//			visited[i] = 1;
//			solution(m + 1, i + 1);
//			visited[i] = 0;
//		}
//	}
}

int main(void) {

	N = 0, M = 0;		// N은 Map의 크기 M은 최대 치킨집 개수
	tmin = 100000000;
	scanf("%d", &N);
	scanf("%d", &M);
	
	


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int input;
			scanf("%d", &input);

			Point temp;
			temp.y = i;
			temp.x = j;
			if (input == 1) {
				home.push_back(temp);
			}
			else if (input == 2) {
				chickenRes.push_back(temp);
			}
		}
	}

	solution(0, 0);
	printf("%d\n", tmin);

	

	return 0;
}

djm03178 5년 전 1

start번째부터 시작하게 되면 결과적으로 최대 13개의 치킨집에서 최대 13개를 고르는 것과 같습니다. 이 중에서 최악은 13C6으로 1716이고, 여기에 정확히는 모르겠지만 함수 호출 횟수로 O(N) 정도가 더 붙지 않을까 싶네요.

hyun353 5년 전 0

그렇다면 처음에 제가 설계했던 부분은 O(13^13)의 시간복잡도를 가지는 것은 맞나요?

djm03178 5년 전 1

그것보단 작은 것 같습니다. O((n+1)!) 이 아닌가 싶네요.

hyun353 5년 전 0

아 정말 감사합니다!!! 도움이 정말 많이됬어요!!

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

문제

문제

출처

ICPC

시간복잡도에 관해 질문이 있습니다.

hyun353 5년 전 0

djm03178 5년 전 1

hyun353 5년 전 0

djm03178 5년 전 1

hyun353 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말