글 읽기 - c++ 40%에서 시간초과가 나요

yulgokyeeyee2 2년 전 0

원리는 bfs비슷하게 하는 대신 함수랑 큐 안 쓰고 해서 코드를 좀 줄였습니다

근데 38에서 시간초과가 나서 조금 더 효율적으로 만들었더니 이번엔 40%에서 시간초과가 나네요 더 어떻게 시간 아낄 수 있을까요

#include <iostream>

using namespace std;

int main() {
	int a, b;
	int c[1010][1010] = { 0 };
	cin >> b >> a;
	for (int i = 1; i <= a; i++) { //토마토박스 정보 받기
		for (int j = 1; j <= b; j++) {
			cin >> c[i][j];
		}
	}
	for (int i = 0; i <= b+1; i++) { //-1로 겉에 장벽두르기
		c[0][i] = -1;
	}
	for (int i = 0; i <= a + 1; i++) {//-1로 겉에 장벽두르기
		c[i][0] = -1;
	}
	for (int i = 0; i <= b + 1; i++) {//-1로 겉에 장벽두르기
		c[a+1][i] = -1;
	}
	for (int i = 0; i <= a + 1; i++) {//-1로 겉에 장벽두르기
		c[i][b+1] = -1;
	}
	int m=1;
	while (1) {//bfs 넓이 누선 탐색
		int hi = 0;//이번 반복에서 익은 토마토의 개수
		for (int i = 1; i <= a; i++) {
			for (int j = 1; j <= b; j++) {
				if (c[i][j] == m) {//토마토가 익은 상태 이며 최근에 익었다면
					if (c[i + 1][j] == 0) {//주변토마토가 안익은 상태라면
						c[i + 1][j] = m+1;//그 토마토를 다음 반복에서 익힌다
						c[i][j] = -1;//한번 탐색한 토마토는 다음반복부터 탐색하지 않는다
						hi++;//이번반복에서 익은 토매토의 개수에 하나를 더한다
					}
					if (c[i - 1][j] == 0) {//위와같음
						c[i - 1][j] = m+1;
						c[i][j] = -1;
						hi++;
					}
					if (c[i][j+1] == 0) {//위와같음
						c[i][j+1] = m+1;
						c[i][j] = -1;
						hi++;
					}
					if (c[i][j-1] == 0) {//위와같음
						c[i][j-1] = m+1;
						c[i][j] = -1;
						hi++;
					}
				}
			}
		}
		if (hi == 0) {//이번 반복에서 익은 토마토가 없음
			for (int i = 0; i <= a + 1; i++) {
				for (int j = 0; j <= b + 1; j++) {
					if (c[i][j] == 0) {//그러한데도 아직안읽은 토마토가 있음 즉 주변이 비어있어 익을 수 없음
						hi = 1;//-1출력후 반복빠져나가기
						break;
					}
				}
				if (hi == 1) {
					break;
				}
			}
			if (hi == 1) {
				cout << -1;
				break;
			}
			else {//안익은 토마토 없음
				cout << m-1;//반복한 횟수출력
				break;//실행 종료
			}
		}
		m++;
	}
}

sjyfantasy 2년 전 0

맵 전체를 계속 탐색해서 그렇습니다.

1인 곳만 찾아서 좌표를 저장하고, 거기서 주변 4좌표를 찾아서 가능한 여부를 찾는게 효율적입니다

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

문제

문제

출처

ICPC

c++ 40%에서 시간초과가 나요

yulgokyeeyee2 2년 전 0

sjyfantasy 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말