글 읽기 - 시간초과 뜨는이유

colorxxx 5년 전 0

최악의 경우 4^8*64 4194304 , 400만정도의 연산이 반복되는데.

제가 작성한 코드에서 253 254번째 줄에서 2번카메라와 5번카메라가 돌아가는 경우를 제한해주지않으면

처음 경우의수를 줄여주지 않으면 9퍼센트정도에서 시간초과가 뜹니다.(제한해주면 시간내에 들어옴)

2*4 ..총 8배의 연산이 더 수행되긴 할테지만 어차피 반복문이 400만밖에 안되는데

1초안에 들어와야 하는 것 아닌가요? 왜 시간초과가 뜨는지 모르겠습니다 ㅠ

혹시라도 복잡도 계산을 잘못한걸까요..

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int ret = 0x7fffffff;
int map[9][9];
int N, M;
struct cam {
	int r, c, num;
};
vector<cam> v;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };

void show() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cout << map[i][j]<<" ";
		}
		cout << endl;
	}
	cout << endl;
}

void acc(){
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (map[i][j] == 0) ans++;
		}
	}
	if (ret > ans) ret = ans;
	//cout << ans<<"\n";
}

void copy(int dst[9][9], int src[9][9]) {
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			dst[i][j] = src[i][j];
		}
	}

}
void see(int idx, int i) {
	if (v[idx].num == 1) {
		int r = v[idx].r; int c = v[idx].c;
		//map[r][c] = -1; //시작위치는 카메라가있다. 카메라정보 저장시킨다 없애지말고
			
		while (1) {
			r = r + dr[i]; c = c + dc[i];
				if (1 <= r&&r <= N && 1 <= c&&c <= M) {
					if (map[r][c] == 0) { //빈자리라면 감시해주고
						map[r][c] = -1;
					}
					else if (map[r][c] == 6) break; //벽 있따면 종료
					//카메라있다면 아무것도 안해주고 다음좌표로 이동
				}
				else break; //범위를 벗어난다면 종료
		}
	}

	else if (v[idx].num == 2) {//0,1만들어온다
		int r = v[idx].r; int c = v[idx].c; 
		
		while (1) {
			r = r + dr[i]; c = c + dc[i];
			if (1 <= r&&r <= N && 1 <= c&&c <= M) {
				if (map[r][c] == 0) { //빈자리라면 감시해주고
					map[r][c] = -1;
				}
				else if (map[r][c] == 6) break; //벽 있따면 종료

												//카메라있다면 아무것도 안해주고 다음좌표로 이동
			}
			else break; //범위를 벗어난다면 종료
		}
	
		r = v[idx].r; c = v[idx].c;
		while (1) {
			r = r + dr[i + 2]; c = c + dc[i + 2];
			if (1 <= r&&r <= N && 1 <= c&&c <= M) {
				if (map[r][c] == 0) { //빈자리라면 감시해주고
					map[r][c] = -1;
				}
				else if (map[r][c] == 6) break; //벽 있따면 종료

												//카메라있다면 아무것도 안해주고 다음좌표로 이동
			}
			else break; //범위를 벗어난다면 종료
		}		



	}

	else if ( v[idx].num == 3) { //0,1,2,3 다 들어올 수 있다.
		int r = v[idx].r; int c = v[idx].c;
		while (1) {
			r = r + dr[i]; c = c + dc[i];
			if (1 <= r&&r <= N && 1 <= c&&c <= M) {
				if (map[r][c] == 0) { //빈자리라면 감시해주고
					map[r][c] = -1;
				}
				else if (map[r][c] == 6) break; //벽 있따면 종료

												//카메라있다면 아무것도 안해주고 다음좌표로 이동

			}
			else break; //범위를 벗어난다면 종료

		}
		r = v[idx].r; c = v[idx].c;
		while (1) {
			r = r + dr[(i+1)%4]; c = c + dc[(i+1)%4];
			if (1 <= r&&r <= N && 1 <= c&&c <= M) {
				if (map[r][c] == 0) { //빈자리라면 감시해주고
					map[r][c] = -1;
				}
				else if (map[r][c] == 6) break; //벽 있따면 종료

												//카메라있다면 아무것도 안해주고 다음좌표로 이동

			}
			else break; //범위를 벗어난다면 종료

		}

	}

	else if (v[idx].num == 4) {
		int r = v[idx].r; int c = v[idx].c;
		while (1) {
			r = r + dr[i]; c = c + dc[i];
			if (1 <= r&&r <= N && 1 <= c&&c <= M) {
				if (map[r][c] == 0) { //빈자리라면 감시해주고
					map[r][c] = -1;
				}
				else if (map[r][c] == 6) break; //벽 있따면 종료

												//카메라있다면 아무것도 안해주고 다음좌표로 이동

			}
			else break; //범위를 벗어난다면 종료

		}
		
		 r = v[idx].r;  c = v[idx].c;
		while (1) {
			r = r + dr[(i+1)%4]; c = c + dc[(i+1)%4];
			if (1 <= r&&r <= N && 1 <= c&&c <= M) {
				if (map[r][c] == 0) { //빈자리라면 감시해주고
					map[r][c] = -1;
				}
				else if (map[r][c] == 6) break; //벽 있따면 종료

												//카메라있다면 아무것도 안해주고 다음좌표로 이동

			}
			else break; //범위를 벗어난다면 종료

		}

		r = v[idx].r;  c = v[idx].c;
		while (1) {
			r = r + dr[(i+2)%4]; c = c + dc[(i+2)%4];
			if (1 <= r&&r <= N && 1 <= c&&c <= M) {
				if (map[r][c] == 0) { //빈자리라면 감시해주고
					map[r][c] = -1;
				}
				else if (map[r][c] == 6) break; //벽 있따면 종료

												//카메라있다면 아무것도 안해주고 다음좌표로 이동

			}
			else break; //범위를 벗어난다면 종료
		}
	}

	else if (v[idx].num == 5) {
		for (int k = 0; k < 4; k++) {
			int r = v[idx].r; int c = v[idx].c;

			while (1) {
				r = r + dr[k]; c = c + dc[k];
				if (1 <= r&&r <= N && 1 <= c&&c <= M) {
					if (map[r][c] == 0) { //빈자리라면 감시해주고
						map[r][c] = -1;
					}
					else if (map[r][c] == 6) break; //벽 있따면 종료

													//카메라있다면 아무것도 안해주고 다음좌표로 이동

				}
				else break; //범위를 벗어난다면 종료

			}
		}
	}

}

void dfs(int idx, int d) {

	int r = v[idx].r; int c = v[idx].c; int num = v[idx].num;
	see(idx, d ); //v[idx]에 있는 카메라가 i 방향을 바라본다.
	//show();
	int tmp[9][9] = { 0, };
	copy(tmp, map);

	if (idx == v.size() - 1) {
		//show();
		acc();
		return;
		
	}
		for (int D = 0; D < 4; D++) {
			if (v[idx+1].num == 2 && (D == 2 || D == 3)) break; //2번카메라는 위아래만존재 
			if (v[idx+1].num == 5 &&  D != 0) break;//5번카메라는 한방향만 존재

			dfs(idx+1, D);
			copy(map, tmp);//원래대로 돌려준다.
			//show();
		}
	
	
}

int main() {
	//ios_base::sync_with_stdio(NULL);
	//cin.tie(NULL);

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0 && map[i][j] != 6) { //빈칸이거나 벽이 아니면
				v.push_back({ i,j,map[i][j] }); //카메라의 정보를 넣는다.
			}
		}
	}
	if (v.size() == 0) {
		acc();
		cout << ret;
		return 0;
	}
	int tmp[9][9] = { 0, };
	copy(tmp, map);
		
	for (int d = 0; d < 4; d++) {
			//if (v[0].num == 2 && (d == 2 || d == 3)) break; //2번카메라는 위아래만존재 
			//if (v[0].num == 5 && d != 0) break;//5번카메라는 한방향만 존재
			dfs(0,d);
			copy(map, tmp);//원래대로 돌려준다.
		}
	
	
	cout << ret;


}

//와...한개도없을경우..너무치사하다

//시간복잡도 분석! 필요하다
//케이스가 분류되는 함수는 꼼꼼히 경우마다 따져줘야한다.
//182-183... k번째마다 초기화해줘야한다.
//이문제..초항 고정이다! ->초항고정안하면 5,6 왜 안나오는가? 어차피 나와야하지않나?
//i+2%4를안해줌.. 복붙하다보니..
//함수 ->돌릴카메라를 정하고->인덱스를 정해줘야한다.. 이중 dfs일경우1
//dfs는 main에서나 dfs나 같은 구조를 띄어야한다! 안띄면 뭔가 이상한 것. 먼저 그려주고 tmp를 저장
//벡터.. v[idx].num idx를 인자로 넘겨주고 벡터의정보를 사용! 이걸걍 idx로36번쨰줄에서 써버림.

//카메라 방향회전하고 ->카메라를 돌리고.. dfs가 2중으로돈다. 이게 뭔가 더 효율적으로 써야할듯?
//v[i] 번째 인덱스를 i번 돌린다.

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

문제

문제

출처

ICPC

시간초과 뜨는이유

colorxxx 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말