글 읽기 - 7576 토마토 시간 초과 질문입니다

minje234 4년 전 0

토마토가 익지 않은 경우 (해당 자리 0 ) 또는 익었지만 더 짧은 일수에 익을 수 있는경우 값이 갱신되게 해놨는데

시간 초과가 뜨네요ㅠ

고민해보다 이유를 모르겠어 질문드립니다. 지적 부탁드립니다..!

#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
int map[1001][1001];
int m, n ;
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
void bfs (int i,int j){
	queue<pair<int,int> > q;
	q.push(pair<int,int>(i,j));
	
	while(!q.empty()){
	i = q.front().first;
	j = q.front().second;
	q.pop();
	for (int k = 0; k < 4; k++){
	if(i+dx[k]>m||i+dx[k]<1||j+dy[k]>n||j+dy[k]<1) continue;
	else if ((map[i+dx[k]][j+dy[k]]==0)||
			map[i+dx[k]][j+dy[k]]>map[i][j]+1)
		{	
			map[i+dx[k]][j+dy[k]]=map[i][j]+1;
			q.push(pair<int,int>(i+dx[k],j+dy[k]));
			
		}
	}
	}
}


int main() {
scanf("%d %d",&n,&m);
for (int i = 1;i<=m;i++){
	for(int j = 1; j<= n ; j++)
	{
		scanf("%d",&map[i][j]);	
	}
}

for (int i = 1;i<=m;i++){
	for(int j = 1; j<= n ; j++)
	{
		if(map[i][j]==1)
			bfs(i,j);	
	}
}
int flag = 0;
int max = 0;
for (int i = 1;i<=m;i++){
	for(int j = 1; j<= n ; j++)
	{
		if(map[i][j]==0)
		{
			flag = 1;
			break;
		}
		if(map[i][j]>max)
			max=map[i][j];
	}
}
if(flag==1) printf("-1");
else printf("%d",max-1);


	
}

djm03178 4년 전 1

정확히 이와 같은 코드를 저격하는 데이터를 제가 https://www.acmicpc.net/board/view/29369 에서 추가했습니다.

저 글의 데이터 생성 코드를 돌려보고, 나오는 데이터를 이 코드에 넣으면 어떤 식으로 동작하게 될지 생각해 보세요.

djm03178 4년 전 2

참고로, "거리가 갱신되면 큐에 넣어준다"는 BFS가 아닙니다. BFS는 오로지 "방문을 안 했으면 가고, 그 이후 다시 방문할 필요가 없어야" 합니다. 즉, 처음으로 어떤 칸에 도달할 때 이미 최단 거리가 확정되어야 합니다.

minje234 4년 전 0

감사합니다 다시 생각해서 해결했습니다!

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

문제

문제

출처

ICPC

7576 토마토 시간 초과 질문입니다

minje234 4년 전 0

djm03178 4년 전 1

djm03178 4년 전 2

minje234 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말