글 읽기 - 감시 시간초과 질문입니다.

zhh1020 5년 전 0

카메라의 종류를 구조체에 넣어주고
dfs를 통해 카메라의 방향을 구성하였습니다.
0 <
1 ^
2 >
3 v 으로 방향을 구성하였습니다.
while문을 통해 map배열의 끝까지 진행하며 벽을 만나면 종료 빈칸일 경우 visit배열에1을 넣고 카메라가 존재하면 continue로 다음칸을 확인하였습니다.
결정된 방향으로 모든 visit을 계산하고 counting을 하였는데 시간초과가 걸립니다!
도와주세요!
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
int map[9][9];
bool visit[9][9];
int ans = 987654321;
int ans_[9];
int cnt = 0;
int wall = 0;
int zerocnt = 0;
struct Info {
	int y, x;
};
Info camera[9];

bool In(int y, int x) {
	return y >= 1 && y <= n && x >= 1 && x <= m && map[y][x] != 6;
}

int DIR[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int couting() {
	int ret = 0;
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= m; x++) {
			if (visit[y][x] == 0)
				ret++;
		}
	}
	return ret;
}
void setting() {
	//카메라 셋팅
	int CNT = zerocnt;
	//cout << endl;
	for (int i = 0; i < cnt; i++) {
		//cout << ans_[i] << " ";
		int dir = ans_[i];
		//cout << dir << " ";
		int cur_x = camera[i].x;
		int cur_y = camera[i].y;
		visit[cur_y][cur_x] = true;

		int cur_num = map[cur_y][cur_x];

		int next_y = cur_y;
		int next_x = cur_x;

		switch (cur_num) {
		case 1:
			if (dir == 0) {
				next_x = cur_x + DIR[dir][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_x += DIR[dir][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[dir][1];
						continue;
					}
					else
						break;
				}
			}
			else if (dir == 1) {
				next_y = cur_y + DIR[dir][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[dir][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[dir][0];
						continue;
					}
					else
						break;
				}
			}
			else if (dir == 2) {
				next_x = cur_x + DIR[dir][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_x += DIR[dir][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[dir][1];
						continue;
					}
					else
						break;
				}
			}
			else if (dir == 3) {
				next_y = cur_y + DIR[dir][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[dir][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[dir][0];
						continue;
					}
					else
						break;
				}
			}
			break;
		case 2:
			if (dir == 0) {
				next_x = cur_x + DIR[dir][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_x += DIR[dir][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[dir][1];
						continue;
					}
					else
						break;
				}

				next_x = cur_x + DIR[2][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_x += DIR[2][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[2][1];
						continue;
					}
					else
						break;
				}

			}

			else if (dir == 1) {
				next_y = cur_y + DIR[dir][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[dir][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[dir][1];
						continue;
					}
					else
						break;
				}

				next_y = cur_y + DIR[3][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[3][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[3][0];
						continue;
					}
					else
						break;
				}
			}
			break;
		case 3:

			if (dir == 0) {
				next_y = cur_y;
				next_x = cur_x + DIR[2][1];
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_x += DIR[2][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[2][1];
						continue;
					}
					else
						break;
				}

				next_y = cur_y + DIR[3][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[3][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[3][0];
						continue;
					}
					else
						break;
				}

			}


			else if (dir == 1) {
				next_y = cur_y;
				next_x = cur_x + DIR[0][1];
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_x += DIR[0][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[0][1];
						continue;
					}
					else
						break;
				}


				next_y = cur_y + DIR[3][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[3][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[3][0];
						continue;
					}
					else
						break;
				}

			}



			else if (dir == 2) {

				next_y = cur_y + DIR[1][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[1][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[1][0];
						continue;
					}
					else
						break;
				}
				next_x = cur_x + DIR[0][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_x += DIR[0][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[0][1];
						continue;
					}
					else
						break;
				}

			}


			else if (dir == 3) {

				next_y = cur_y;
				next_x = cur_x + DIR[2][1];
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_x += DIR[2][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[2][1];
						continue;
					}
					else
						break;
				}

				next_y = cur_y + DIR[1][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[1][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[1][0];
						continue;
					}
					else
						break;
				}

			}

			break;


		case 4:
			if (dir == 0) {


				next_y = cur_y + DIR[1][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[1][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[1][0];
						continue;
					}
					else
						break;
				}
				next_x = cur_x + DIR[2][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_x += DIR[2][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[2][1];
						continue;
					}
					else
						break;
				}

				next_y = cur_y + DIR[3][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0) {
						visit[next_y][next_x] = true;
						next_y += DIR[3][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[3][0];
						continue;
					}
					else
						break;
				}

			}






			else if (dir == 1) {

				next_x = cur_x + DIR[0][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0 && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						next_x += DIR[0][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[0][1];
						continue;
					}
					else
						break;
				}

				next_x = cur_x + DIR[2][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0 && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						next_x += DIR[2][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[2][1];
						continue;
					}
					else
						break;
				}

				next_y = cur_y + DIR[3][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0 && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						next_y += DIR[3][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[3][0];
						continue;
					}
					else
						break;
				}

			}



			else if (dir == 2) {

				next_y = cur_y + DIR[1][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0 && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						next_y += DIR[1][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[1][0];
						continue;
					}
					else
						break;
				}
				next_x = cur_x + DIR[0][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0 && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						next_x += DIR[0][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[0][1];
						continue;
					}
					else
						break;
				}

				next_y = cur_y + DIR[3][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0 && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						next_y += DIR[3][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[3][0];
						continue;
					}
					else
						break;
				}

			}


			else if (dir == 3) {
				next_x = cur_x + DIR[0][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0 && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						next_x += DIR[0][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[0][1];
						continue;
					}
					else
						break;
				}

				next_x = cur_x + DIR[2][1];
				next_y = cur_y;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0 && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						next_x += DIR[2][1];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_x += DIR[2][1];
						continue;
					}
					else
						break;
				}

				next_y = cur_y + DIR[1][0];
				next_x = cur_x;
				while (1) {
					if (In(next_y, next_x) && map[next_y][next_x] == 0 && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						next_y += DIR[1][0];
						CNT--;
					}
					else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
						next_y += DIR[1][0];
						continue;
					}
					else
						break;
				}

			}
			break;



		case 5:

			dir = 0;
			next_x = cur_x + DIR[dir][1];
			next_y = cur_y;
			while (1) {
				if (In(next_y, next_x) && map[next_y][next_x] == 0) {
					visit[next_y][next_x] = true;
					next_x += DIR[dir][1];
					CNT--;
				}
				else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
					next_x += DIR[dir][1];
					continue;
				}
				else
					break;
			}
			dir = 1;
			next_y = cur_y + DIR[dir][0];
			next_x = cur_x;
			//cout << next_y << " " << next_x << endl;
			while (1) {
				if (In(next_y, next_x) && map[next_y][next_x] == 0) {
					visit[next_y][next_x] = true;
					next_y += DIR[dir][0];
					CNT--;
				}
				else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
					next_y += DIR[dir][0];
					continue;
				}
				else
					break;
			}
			dir = 2;
			next_x = cur_x + DIR[dir][1];
			next_y = cur_y;
			while (1) {
				if (In(next_y, next_x) && map[next_y][next_x] == 0) {
					visit[next_y][next_x] = true;
					next_x += DIR[dir][1];
					CNT--;
				}
				else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
					next_x += DIR[dir][1];
					continue;
				}
				else
					break;
			}
			dir = 3;
			next_y = cur_y + DIR[dir][0];
			next_x = cur_x;
			while (1) {
				if (In(next_y, next_x) && map[next_y][next_x] == 0) {
					visit[next_y][next_x] = true;
					next_y += DIR[dir][0];
					CNT--;
				}
				else if (In(next_y, next_x) && map[next_y][next_x] >= 1 && map[next_y][next_x] <= 5) {
					next_y += DIR[dir][0];
					continue;
				}
				else
					break;
			}

			break;
		}


	}
	//cout << endl;

	CNT = couting();
	//cout << CNT << endl;
	if (CNT - wall < ans)
		ans = CNT - wall;

}

void dfs(int depth) {
	if (depth >= cnt ) {
		
		setting();
		memset(visit, false, sizeof(visit));
		return;
	}

	int value = map[camera[depth].y][camera[depth].x];
	switch (value) {
	case 2:
		for (int i = 0; i < 2; i++) {
			ans_[depth] = i;
			dfs(depth + 1);
		}
		break;
	case 1:
	case 3:
	case 4:
		for (int i = 0; i < 4; i++) {
			ans_[depth] = i;
			dfs(depth + 1);
		}
		break;
	case 5:
		ans_[depth] = 0;
		dfs(depth + 1);
		break;
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n >> m;


	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= m; x++) {
			cin >> map[y][x];
			if (map[y][x] >= 1 && map[y][x] <= 5) {
				camera[cnt].x = x;
				camera[cnt++].y = y;
			}
			else if (map[y][x] == 0)
				zerocnt++;
			else if (map[y][x] == 6)
				wall++;
		}
	}

	dfs(0);
	cout << ans;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

감시 시간초과 질문입니다.

zhh1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
