글 읽기 - 토마토 시간초과 c++(이런 것 물어 봐도 괜찮나요)

hs9200 3년 전 0

다시 올려요

저가 잘 못해서...

왜 시간초과가 나는 지 모르겠어요

도와주세요

저 한지 얼마 안 됐어요...

#include <stdio.h>
#include <algorithm>
#include <queue>
#define M 1000//배열 크기
#define INF 599999999//다이내믹 최소값 구해야 하기 때문
using namespace std;
queue <int> q;
int a[M + 1][M + 1];//배열
int d[M + 1][M + 1];//다이내믹 배열
int dy[4] = { 0,1,0,-1 };//4방향 데이터
int dx[4] = { 1,0,-1,0 };//4방향 데이터
int ty, tx, y, x;//bfs에 필요한 변수
int maxa, n, m;//가로세로길이, 가장 큰 값
int main(void)
{
	int i, j;
	scanf("%d %d", &m, &n);//배열 크기(가로를 먼저 입력 받아야 함)
	int sy, sx;//찾은 지점이 1이면 queue에 넣는 형태로
	for (i = 1; i <= n; i++)//for문 시작
	{
		for (j = 1; j <= m; j++)//for문 시작 2
		{
			scanf("%d", &a[i][j]);//이건 배열 입력 받는것(토마토에서 1,0,-1 입력 받는것)
			if (a[i][j] != -1)//a[i][j]가 토마토가 없는 지점이 아니면
			{
				d[i][j] = INF;//가장 빨리 토마토가 익는 시간을 구해야 하므로 최솟값이기 때문에
			}
			else//토마토가 없으면
			{
				d[i][j] = -1;//아예 다이내믹에 포함 x(그러니까 최솟값이 항상 변하지 않는다(-1보다 작은 거리는 없으므로))
			}
		}
	}
	for (sy = 1; sy <= n; sy++)//for문으로 값이 1인 지점을 찾는다
	{
		for (sx = 1; sx <= m; sx++)//for문으로 값이 1인 지점을 찾는다 2
		{
			if (a[sy][sx] == 1)//만약 토마토가 익었으면
			{
				q.push(sy);//queue에 집어 넣고
				q.push(sx);//queue에 집어 넣고 2
				d[sy][sx] = 0;//처음부터 익었으니까
				a[sy][sx] = 2;//이미 다녀왔다고 visit
				while (!q.empty())
				{
					y = q.front(); q.pop();//queue를 꺼낸다
					x = q.front(); q.pop();//queue를 꺼낸다2
					for (i = 0; i <= 3; i++)//4방향이니까 for문 돌리고
					{
						ty = y + dy[i];//목표 y좌표 구한다
						tx = x + dx[i];//목표 x좌표 구한다
						if (ty >= 1 && ty <= n && tx >= 1 && tx <= m && a[ty][tx] != -1 && a[ty][tx] != 1 && d[ty][tx] > d[y][x] + 1)
						//이건 배열 밖을 벗어나면 안되고, 토마토가 없으면 안되고, 익은 토마토면(다녀오지 않은) 안되고(
                        //나중에 다녀와야 하니까) 거리가 더 짧아야 하니까
                        {
							d[ty][tx] = d[y][x] + 1;//다이내믹
							q.push(ty);//queue에 집어 넣고 3
							q.push(tx);//queue에 집어 넣고 4
							a[ty][tx] = 2;//이미 다녀왔다고 visit
						}
					}
				}
			}
		}
	}
	maxa = -1;
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			if (maxa < d[i][j])
			{
				maxa = d[i][j];
			}
		}
	}
    //가장 오래 걸리는 토마토(모든 토마토가 다 익는 시점)
	if (maxa == INF)//안 익은토마토가 있으니까
	{
		printf("-1");
	}
	else if (maxa == 0)//토마토가 처음부터 모두 익었을 때
	{
		printf("0");
	}
	else//일반의 경우
	{
		printf("%d", maxa);
	}
	return 0;//끝
}

rhdqor213 3년 전 0

질문은 중복해서 올리지 않는 것이 좋습니다.

uc07012hi 3년 전 0

34-36 번째 라인에서 익은 토마토를 찾기 위해서 for문을 돌리셨는데 최악의 경우 시간이 너무 오래 걸리는 것 같습니다.

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

문제

문제

출처

ICPC

토마토 시간초과 c++(이런 것 물어 봐도 괜찮나요)

hs9200 3년 전 0

rhdqor213 3년 전 0

uc07012hi 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말