글 읽기 - 시간 초과가 왜 나는 걸까요

gmlwjd7879 4년 전 0

다른 사람 코드 참고해봐도 다들 비슷한거 같은데 도대체 왜 시간초과가 뜨는지 모르겠어요,,

#include <stdio.h>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int N, M, zero, ans = 9999999;
int box[50][50], visited[50][50], flag[10];
int dx[] = { -1,0,0,1 }, dy[] = { 0,-1,1,0 };
//queue <pair<int, int>> q;
vector <pair<int, int>> v;

void bfs(queue<pair<int, int>> q) {
	int time = 0, cnt = 0;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i], yy = y + dy[i];
			if (xx >= 0 && xx < N && yy >= 0 && yy < N) {	//경계조건 조사
				if (box[xx][yy] != 1 && visited[xx][yy] == -1) {	//벽이 아닌 곳을 방문한 적이 없다면(비활성상태이면)
					visited[xx][yy] = visited[x][y] + 1;		//활성상태로 전환 & 시간 추가
					if (box[xx][yy] == 0) {		//빈칸이면 바이러스 확산
						cnt++;
						time = visited[xx][yy];
					}
					q.push({ xx,yy });
				}
			}
		}
	}
	if (time < ans && cnt == zero)		//빈칸이 모두 채워지고 시간이 더 적다면
		ans = time;
}
void distribution(int idx, int vcnt) {
	if (vcnt == M) {
		queue <pair<int, int>> q;
		memset(visited, -1, sizeof(visited));		//바이러스 퍼지는 시간
		for (int i = 0; i < v.size(); i++) {
			if (flag[i]) {		//선택한 곳이면
				q.push({ v[i].first,v[i].second });
				visited[v[i].first][v[i].second] = 0;		//활성화
			}
		}
		bfs(q);
		return;
	}
	for (int i = idx; i < v.size(); i++) {		//인덱스로만 판별
		if (!flag[i]) {		//선택한 적이 없으면
			flag[i] = true;
			distribution(idx + 1, vcnt + 1);
			flag[i] = false;
		}
	}
}
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &box[i][j]);
			if (box[i][j] == 2)		//바이러스를 놓을 수 있는 공간
				v.push_back({ i,j });
			else if (box[i][j] == 0) zero++; //빈칸의 갯수
		}
	}
	distribution(0, 0);
	if (ans != 9999999)
		printf("%d\n", ans);
	else
		printf("%d\n", -1);
	return 0;
}

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

문제

문제

출처

ICPC

시간 초과가 왜 나는 걸까요

gmlwjd7879 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말