글 읽기 - 무슨 짓을 해도 7%에서 시간초과가 뜨네요ㅠㅠㅠ

jay531 3년 전 0

테스트 케이스는 얼추 맞는 것 같은데 계속 시간초과가 뜨네요. 출력이 오래 걸리는 건 아니라서 그냥 ios_sync로 해결했는데...어디서 시간이 오래 걸릴까요?

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

struct MOV{
	int x, y;
};

bool ans_flag = false;

int N, L, R, cnt=1, ans;
int mat[101][101];
int visited[101][101];
queue< pair<int, int> > q, t;
MOV mov[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

void print(){

	cout << endl;
	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){
			cout << visited[i][j] << " ";
		}
		cout << endl;
	}
}

void check(int a, int b){

	visited[a][b] = cnt;
	int sum=0;
	int count=0;

	q.push( make_pair(a, b) );
	t.push( make_pair(a, b) );


	while(!q.empty()){

		count++;

		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		sum+=mat[x][y];

		for(int i=0;i<4;++i){

			int nx = x + mov[i].x;
			int ny = y + mov[i].y;

			int val = abs(mat[x][y] - mat[nx][ny]);

			if(0<=nx && nx<N && 0<=ny && ny<N && visited[nx][ny] == 0 && L<=val && val<=R){

				visited[nx][ny] = cnt;
				q.push( make_pair(nx, ny) );
				t.push( make_pair(nx, ny) );				
			}

		}
	}

	while(!t.empty()){

		mat[t.front().first][t.front().second] = sum/count;
		t.pop();
	}

}

int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> L >> R;

	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){
			cin >> mat[i][j];
		}
	}	

	while(!ans_flag){


		for(int i=0;i<N;++i){
			memset(visited[i], false, sizeof(int)*N);
		}

		/* 모든 연합 확인 */
		for(int i=0;i<N;++i){
			for(int j=0;j<N;++j){

				if(visited[i][j] == 0){
					check(i, j);
					cnt++;	
				}

			}
		}

		bool is_same = false;

		for(int i=0;i<N;++i){
			for(int j=0;j<N;++j){

				int nx = i + mov[i].x;
				int ny = j + mov[i].y;

				if( 0<=nx && nx<N && 0<=ny && ny<N && visited[i][j] == visited[nx][ny] ){
					is_same = true;
					break;
				}

			}
		}

		if(is_same == true){
			ans++;
		}
		else
			ans_flag = true;
	}

	cout << ans << endl;

	return 0;
}

exponential_e 3년 전 1

문제가 자세히 기억은 안나서 다른 건 잘 모르겠지만 113, 114번째 줄에 mov 배열이 i값으로 접근되고 있는데, 그러면 110번째 줄은 오타인 것 같습니다.

jay531 3년 전 1

엌ㅋㅋㅋ 오타 고치니까 바로 맞았습니다. 감사해요!

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

문제

문제

출처

ICPC

무슨 짓을 해도 7%에서 시간초과가 뜨네요ㅠㅠㅠ

jay531 3년 전 0

exponential_e 3년 전 1

jay531 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말