글 읽기 - 토마토 문제 질문

joon8409 8년 전 0

이것을 큐를 사용해서 풀었는데 어떻게 해야 시간초과를 풀수 있을지 모르겠습니다.

매번 아직 안익은 애들을 큐 두개를 통해서 번갈아 가면서 저장한다음에

바뀔애들은 temp에 집어넣어서 한꺼번에 바꿉니다.

시간초과를 어떻게 해결해야할까요..?

#include<iostream>
#include<cstdio>
#include <queue>
using namespace std;
int map[1001][1001] = { 0, };
int main(void)
{
	int h, w;
	cin >> h >> w;
	queue<pair<int, int> > Q[2]; //큐에는 매번 안익은 애들이 저장됨
	queue<pair<int, int> > temp; //매번 익을 넘들을 저장해서 한턴이 지나갈때마다 그를 반영
	bool convert = false;
	int b = 0;
	int t = 0;
	bool notconverted = true;
	int dx[8] = { 0,0,1,-1 }, dy[8] = { -1,1,0,0 };
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 0)
			{
				Q[b].push(make_pair(i, j));
			}
		}
	}
	while (!Q[b].empty())
	{
		while (!Q[b].empty())
		{
			pair<int, int> p = Q[b].front();
			Q[b].pop();
			int i = p.first, j = p.second;
			for (int v = 0; v < 4; v++)
			{
				int x= i + dx[v], y = j + dy[v];
				if (map[x][y]==1) {
					convert = true;
					notconverted = false;
				}
			}
			if (!convert)
			{
				Q[!b].push(make_pair(i, j));
			}
			else {
				temp.push(make_pair(i, j));
			}
			convert = false;

		}
		while (!temp.empty())
		{
			pair<int, int> p = temp.front();
			temp.pop();
			int i = p.first, j = p.second;
			map[i][j] = 1;
		}
		if (notconverted)
		{
			break;
		}

		b = !b;
		t++;
		notconverted = true;
	}
	if (!Q[b].empty() || !Q[!b].empty())
	{
		cout << -1;
	}
	else {
		cout << t;
	}
}

whgusfud 8년 전 0

저는 이 문제를 풀 때,

1. 처음에 익었다고 주어진 애들을 큐에 넣기.

2. 2차원 배열에 토마토가 없는 곳인지 있는데 익어있는지, 안익어있는지 표시.

3. q.front()의 4방향에 안익은 토마토가 있다면 큐에 넣고 front()는 없애줍니다.

이런식으로 했을 때 통과 받았어요.

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

문제

문제

출처

ICPC

토마토 문제 질문

joon8409 8년 전 0

whgusfud 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말