글 읽기 - 연구소 조합 생성으로 풀었는데 시간초과..

gmlwndla97 4년 전 0

예전에 제출했던 맞은 코드와 비교해보면 벽을 3개 세우는걸 permutation으로 구현한 차이 밖에 없는거 같은데 ㅜㅜ 이것때문에 시간초과가 나는건가요?? 아니면 어디서 시간초과가 나는건가요ㅠㅠ

#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<memory.h>
#include<stack>
#include<stdio.h>
#include<math.h>
#include<functional>
#include<string>
#pragma warning(disable: 4996)
using namespace std;
int map[9][9];
int origin[9][9];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n, m;
int maxval = 0;
vector<pair<int, int>> v;
queue<pair<int, int>> q;
void bfs() {
	while (!q.empty()) {
		int now_x = q.front().first;
		int now_y = q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			int nx = dx[i] + now_x;
			int ny = dy[i] + now_y;
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if ( map[nx][ny] == 0) {
					map[nx][ny] = 2;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) {
				v.push_back(make_pair(i, j));
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			origin[i][j] = map[i][j];
		}
	}
	int* selected = new int[v.size()];
	fill(selected, selected + 3, 1);
	sort(selected, selected + v.size());
	do {
		
		for (int i = 0; i < v.size(); i++) {
			if (selected[i] == 1) {
				int x, y;
				x = v[i].first;
				y = v[i].second;
				map[x][y] = 1;
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 2) {
					q.push(make_pair(i, j));
				}
			}
		}
		bfs();
		
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0) {
					cnt++;
				}
			}
		}
		maxval = max(maxval, cnt);
		cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = origin[i][j];
			}
		}
	} while (next_permutation(selected, selected + v.size()));
	cout << maxval << '\n';
	return 0; 
}

gmlwndla97 4년 전 0

57번째 줄만 바꾸니까 정답처리되네요ㅠㅠ

전역변수로 int selected[64]로 바꾸니까 해결되었습니다..

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

문제

문제

출처

ICPC

연구소 조합 생성으로 풀었는데 시간초과..

gmlwndla97 4년 전 0

gmlwndla97 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말