글 읽기 - 2468번 잘못된 케이스좀 찾아주세요

meme0724 9년 전 0

높이 K만큼의 홍수가 일어날 때마다 safe함수로 안전구역을 찾아냅니다

일단 안전 구역을 한 자리 찾으면 bfs를 진행하여 한 구역을 전부 찾고 그때마다 count를 증가시켜서 안전영역의 개수를 셉니다.

check배열은 이미 확인을 진행한 안전 구역인지를 확인하는 배열로 만들었습니다.

그런데 틀렸습니다라고 뜨는데 제가 어느 부분을 미처 생각 못했는지 잘 모르겠네요...

그리고 이걸 고쳐서 제출한다고 해도 시간초과가 나올 거 같은데

여기서 시간을 더 줄일 방법이나 시간복잡도가 더 적은 알고리즘을 가르쳐 주시면 감사하겠습니다 꾸벅

#include <stdio.h>
#include <queue>
using namespace std;

int a[102][102], check[102][102] = { { 0, }, }, n;
void safe(int x, int y, int level)
{
	queue<int> qx;	queue<int> qy;
	qx.push(x); qy.push(y);

	while (qx.size() != 0)
	{
		if (check[qx.front() + 1][qy.front()] == 0 && qx.front() < n && a[qx.front() + 1][qy.front()] > level)
		{
			check[qx.front() + 1][qy.front()] = 1;
			qx.push(qx.front() + 1);    qy.push(qy.front());
		}
		if (check[qx.front()][qy.front() + 1] == 0 && qy.front() < n && a[qx.front()][qy.front() + 1] > level)
		{
			check[qx.front()][qy.front() + 1] = 1;
			qx.push(qx.front());   qy.push(qy.front() + 1);
		}
		if (check[qx.front() - 1][qy.front()] == 0 && qx.front() > 1 && a[qx.front() - 1][qy.front()] > level)
		{
			check[qx.front() - 1][qy.front()] = 1;
			qx.push(qx.front() - 1);    qy.push(qy.front());
		}
		if (check[qx.front()][qy.front() - 1] == 0 && qy.front() > 1 && a[qx.front()][qy.front() - 1] > level)
		{
			check[qx.front()][qy.front() - 1] = 1;
			qx.push(qx.front());   qy.push(qy.front() - 1);
		}
		qx.pop(); qy.pop();
	}

}
int main()
{
	int i, j, k, max = -1, count = 0, ans = -1 ;

	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			scanf("%d", &a[i][j]);
			if (max < a[i][j])
				max = a[i][j];
		}
	}

	for (k = 1; k <= max; k++)
	{
		count = 0;
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				check[i][j] = 0;
			}
		}
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				if (check[i][j] == 0 && a[i][j] > k)
				{
					check[i][j] = 1;
					safe(i, j, k); count++;
				}
			}
		}
		if (count > ans)
			ans = count;
	}
	printf("%d", ans);
	return 0;
}

dudn134 9년 전 2

1 1 1 1 1

하면 0 나오네요.

meme0724 9년 전 0

52째줄에 k=0으로 바꾸니까 정답이 나오네요!!

저게 시간 안에 풀릴 줄은 몰랐는데 그래도 감사드려요!!

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

문제

문제

출처

ICPC

2468번 잘못된 케이스좀 찾아주세요

meme0724 9년 전 0

dudn134 9년 전 2

meme0724 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말