글 읽기 - 2638번 치즈 질문

waylight3 8년 전 0

이 문제의 골칫거리인 치즈 내부 공기를 구하는 게 더 귀찮을 것 같아서

(0, 0)에서 시작해 공기가 점점 퍼진다고 생각하고, 공기가 닿을 때 마다 치즈 값을 1씩 늘리는 방식으로 했습니다.

그럼 결국 맵 전체중 값이 2보다 큰 것들을 지우면 되니까요.

한 번 지난 지점을 다시 검사하지 않으려고 -1을 넣었으며 이는 Revive() 함수에서 0으로 다시 바꿔줍니다.

그리고 치즈 개수를 최대한 적은 연산으로 세려고 Revive() 함수에서 같이 계산하구요.

근데 이 문제를 이렇게 시뮬레이션 하는 거 말고도 방법이 있나요?? 한 77% 채점하다가 시간초과가 뜨네요 ㅠㅠ

나름 필요없는 과정들 빼고 최대한 빠르게 만든건데 계속 걸리네요... (아니면 코드를 잘못 짠건지)

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;

int mapp[101][101] = { 0 };
int w, h;

void Erase(int y, int x)
{
	if (x < 0 || x > w || y < 0 || y > w) { return; }

	if (mapp[y][x] == 0)
	{
		mapp[y][x] = -1;

		Erase(y - 1, x);
		Erase(y + 1, x);
		Erase(y, x - 1);
		Erase(y, x + 1);
	}
	else if (mapp[y][x] > 0)
	{
		mapp[y][x] += 1;
	}
}

int Revive()
{
	int cheese = 0;

	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			if (mapp[y][x] == 2 || mapp[y][x] == 1) { mapp[y][x] = 1; cheese++; }
			else { mapp[y][x] = 0; }
		}
	}

	return cheese;
}

int main()
{
	int count = 0, cheese = 0;

	cin >> h >> w;

	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			cin >> mapp[y][x];
		}
	}

	while (true)
	{
		Erase(0, 0);
		cheese = Revive();
		count++;
		if (cheese == 0) { break; }
	}

	cout << count;

	return 0;
}

kesakiyo 8년 전 0

Erase 함수에 아주 심각한 오류가 있습니다.

x의 범위는 [0, w) 이고 y의 범위는 [0, h) 입니다.

이를 유의해서 코딩을 해 주어야 합니다.

waylight3 8년 전 0

이런! y 범위를 벗어났나 체크할 때 h가 아니라 w를 적어놨었네요;;

덕분에 오류 해결했어요! 감사합니다.

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

문제

문제

출처

ICPC

2638번 치즈 질문

waylight3 8년 전 0

kesakiyo 8년 전 0

waylight3 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말