글 읽기 - 안녕하세요 시간초과 질문입니다

baepoce 3년 전 0

시간초과 원인을 모르겠습니다..

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

int n, m;
int arr[101][101]; //치즈배열
int map[101][101]; //공기배열
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
bool visit[101][101];

queue<pair<int, int>> q;
void bfs() { //공기 체크 
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if ((nx<1 || ny<1 || nx>n || ny>m))
				continue;
			if (!visit[nx][ny] && arr[nx][ny] == 0) {
				q.push({ nx,ny });
				visit[nx][ny] = true;
				map[nx][ny] = 1;
			}
		}
	}

}
int main() {
	int ans = 0;
	int cheese = 0;
	int remove = 0;
	int remain = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1)
				cheese++;
		}
	}
	q.push({ 1,1 });
	visit[1][1] = true;
	map[1][1] = 1;
	while (cheese>0) {
		vector<pair<int, int>> vec;
		bfs();
		for (int x = 1; x <= n; x++) {  //없어질 치즈찾기
			for (int y = 1; y <= n; y++) {
				if (arr[x][y] == 1) {
					for (int i = 0; i < 4; i++) {
						int nx = x + dx[i];
						int ny = y + dy[i];
						if (nx<1 || ny<1 || nx>n || ny>m)
							continue;
						if (map[nx][ny] == 1) {
							vec.push_back({ x,y });
							break;
						}
					}
				}
			}
		}
		remove = vec.size();
		for (int i = 0; i < vec.size(); i++) {
			int x = vec[i].first;
			int y = vec[i].second;
			arr[x][y] = 0;
			q.push({ x,y });
			visit[x][y] = true;
			map[x][y] = 1;
		}
		remain = remove;
		cheese -= remove;
		ans++;
	}
	cout << ans << "\n";
	cout << remain;
}
	

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

문제

문제

출처

ICPC

안녕하세요 시간초과 질문입니다

baepoce 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말