글 읽기 - C언어 시간초과 ....

leejun332211 5년 전 1

ㄹ잘푼거 같은데... 시간초과가 나옵니다. 반례도 없고 잘되는데... 이런경우 어떻게 해결해야하나요 ..답답 ㅠㅠ

#include <stdio.h>

int okay(int a[2][1001][1001],int b, int c){
	int i,j;
	int result=1;
	
	for(i=0;i<b; i++){
		for(j=0; j<c; j++){
				if(a[0][i][j]==0){
						result=0;
						break;
				}
		}
	}
	
	return result;
}
//배열, 세로사이즈, 가로사이즈, 세로 좌표, 가로 좌표
void change(int a[2][1001][1001],int b, int c, int d, int e){
	if(d>=0&&e>=0&&d<=b&&e<=c&&(a[0][d][e]==0)){
		a[0][d][e]=1;
		a[1][d][e]=1;	
	}
}




int main(){
	int arr[2][1001][1001];

	
	int a,b;
	int i,j,l;
	int count=0;
	int k=0;
	
	scanf("%d %d",&a,&b);
	
	for(i=0;i<b;i++){
		for(j=0; j<a; j++){
			scanf("%d ",&arr[0][i][j]);
		}
	}
	
	
	
	while(1){
		
	for(i=0; i<1001; i++){
		for(j=0; j<1001; j++){
			arr[1][i][j]=0;
		}
	}
		
		k=okay(arr,b,a);
		if(k==1){
		break;
		}
		count++;
	for(i=0; i<b; i++){
		for(j=0; j<a; j++){
			
			if(arr[0][i][j]==1&&arr[1][i][j]==0){
				change(arr,b,a,i-1,j);
				change(arr,b,a,i+1,j);
				change(arr,b,a,i,j-1);
				change(arr,b,a,i,j+1);
			}
		}
	}
		if(count==1001*1001){
		count=-1;
		break;
		}
	

		
	}
	
	printf("%d",count);





return 0;
}

eric00513 5년 전 0

시간초과가 나온 이유는 당연합니다. 지금 while문이랑 이중 for이 있으시죠? 게다가 그 안에 이중 for가 두 개 있으며 처리하는 개수가 3개가 넘습니다. 이 모두를 곱하면 1초 안에 처리할 수 있는 개수인 1억을 넘을 것입니다. (n=m=1000)으로 생각했을 때

eric00513 5년 전 0

시간초과가 나오는데, 반례가 없을 수 없습니다. 엄청 큰 데이터가 있으니까 시간초과가 나는 것입니다.

leejun332211 5년 전 1

ㄱㄷ속도를 위해 줄여봤습니다..

#include <stdio.h>

int okay(int a[2][1001][1001],int b, int c){
	int i,j;
	int result=1;
	
	for(i=0;i<b; i++){
		for(j=0; j<c; j++){
				if(a[0][i][j]==0){
						result=0;
						break;
				}
		}
	}
	
	return result;
}
//배열, 세로사이즈, 가로사이즈, 세로 좌표, 가로 좌표
void change(int a[2][1001][1001],int b, int c, int d, int e){
	if(d>=0&&e>=0&&d<=b&&e<=c&&(a[0][d][e]==0)){
		a[0][d][e]=1;
		a[1][d][e]=1;	
	}
}

void copy(int from[2][1001][1001], int to[2][1001][1001], int c, int d){
	int i,j;
	
	for(i=0; i<c; i++){
		for(j=0; j<d; j++){
			to[0][i][j]=from[0][i][j];
		}
	}
}

int same(int a[2][1001][1001],int b[2][1001][1001],int c, int d){
	int i, j;
	int result=1;
	
	for(i=0; i<c; i++){
		for(j=0; j<d; j++){
			if(a[0][i][j]!=b[0][i][j]){
				result=0;
				break;
			}
		}
	}
	return result;
}



int main(){

	int arr[2][1001][1001];
	int arr2[2][1001][1001];
	
	int a,b;
	int i,j,l;
	int count=0;
	int k=0;
	
	scanf("%d %d",&a,&b);
	
	for(i=0;i<b;i++){
		for(j=0; j<a; j++){
			scanf("%d ",&arr[0][i][j]);
		}
	}
	
	
	
	while(1){
	
	copy(arr,arr2,b,a);
		
	for(i=0; i<1001; i++){
		for(j=0; j<1001; j++){
			arr[1][i][j]=0;
		}
	}
		
		k=okay(arr,b,a);
		if(k==1){
		break;
		}
		count++;
	for(i=0; i<b; i++){
		for(j=0; j<a; j++){
			
			if(arr[0][i][j]==1&&arr[1][i][j]==0){
				change(arr,b,a,i-1,j);
				change(arr,b,a,i+1,j);
				change(arr,b,a,i,j-1);
				change(arr,b,a,i,j+1);
			}
		}
	}

	if(same(arr,arr2,b,a)){
	count=-1;
	break;
	}
	

		
	}
	
	printf("%d",count);





return 0;
}

eric00513 5년 전 0

여전히 시간 초과네요 구현 방법을 바꿔보세요 게시판 검색에 "토마토" 검색하시면, 최근에 올라온 글이 있는데, 그 글들 살펴 보세요

leejun332211 5년 전 1

안되었습니다.... 또 줄였는데... 이상하네요 ..;;

#include <stdio.h>

int okay(int a[2][1000][1000],int b, int c){
	int i,j;
	int result=1;
	
	for(i=0;i<b; i++){
		for(j=0; j<c; j++){
				if(a[0][i][j]==0){
						result=0;
						break;
				}
		}
	}
	
	return result;
}
//배열, 세로사이즈, 가로사이즈, 세로 좌표, 가로 좌표
void change(int a[2][1000][1000],int b, int c, int d, int e){
	if(d>=0&&e>=0&&d<=b&&e<=c&&(a[0][d][e]==0)){
		a[0][d][e]=1;
		a[1][d][e]=1;	
	}
}

void copy(int from[2][1000][1000], int to[2][1000][1000], int c, int d){
	int i,j;
	
	for(i=0; i<c; i++){
		for(j=0; j<d; j++){
			to[0][i][j]=from[0][i][j];
		}
	}
}

int same(int a[2][1000][1000],int b[2][1000][1000],int c, int d){
	int i, j;
	int result=1;
	
	for(i=0; i<c; i++){
		for(j=0; j<d; j++){
			if(a[0][i][j]!=b[0][i][j]){
				result=0;
				break;
			}
		}
	}
	return result;
}



int main(){

	int arr[2][1000][1000];
	int arr2[2][1000][1000];
	
	int a,b;
	int i,j,l;
	int count=0;
	int k=0;
	
	scanf("%d %d",&a,&b);
	
	for(i=0;i<b;i++){
		for(j=0; j<a; j++){
			scanf("%d ",&arr[0][i][j]);
		}
	}
	
	
	
	while(1){
	
	copy(arr,arr2,b,a);
		
	for(i=0; i<b; i++){
		for(j=0; j<a; j++){
			arr[1][i][j]=0;
		}
	}
		
		k=okay(arr,b,a);
		if(k==1){
		break;
		}
		count++;
	for(i=0; i<b; i++){
		for(j=0; j<a; j++){
			
			if(arr[0][i][j]==1&&arr[1][i][j]==0){
				change(arr,b,a,i-1,j);
				change(arr,b,a,i+1,j);
				change(arr,b,a,i,j-1);
				change(arr,b,a,i,j+1);
			}
		}
	}

	if(same(arr,arr2,b,a)){
	count=-1;
	break;
	}
	

		
	}
	
	printf("%d",count);





return 0;
}

eric00513 5년 전 0

https://www.acmicpc.net/board/...

참고 링크입니다/

eric00513 5년 전 0

BFS 알고리즘은 알고 계시면 다행이에요

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

문제

문제

출처

ICPC

C언어 시간초과 ....

leejun332211 5년 전 1

eric00513 5년 전 0

eric00513 5년 전 0

leejun332211 5년 전 1

eric00513 5년 전 0

leejun332211 5년 전 1

eric00513 5년 전 0

eric00513 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말