글 읽기 - 안전영역 질문드립니다.

lsk4393 3년 전 0

범위를 0부터 최대까지 돌리면 정답이 맞습니다.. 근데 왜 높이의 최소부터 최대까지 하면 ... 75%정도에서 오답이 되는지 모르겠어요...

최소높이부터 시작해야 안전영역이 생긴다고 생각을 했는데.. 이게 아닌건가요.. ㅠㅠ

#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

#define endl "\n"

int N;
int map[101][101];
int copy_map[101][101];
int visit[101][101];

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int max_val = 0;
int min_val = 987654321;

int ans = -1;

void bfs(int r, int c)
{
	visit[r][c] = true;
	queue<pair<int, int>> q;
	q.push({ r,c });

	while (!q.empty())
	{
		int size = q.size();

		while (size--)
		{
			int x = q.front().first;
			int y = q.front().second;

			q.pop();

			for (int i = 0; i < 4; i++)
			{
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx < 0 || ny < 0 || nx >= N || ny >= N)
					continue;
				if (visit[nx][ny])
					continue;
				if (!copy_map[nx][ny])
					continue;

				visit[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}
}

void func()
{
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (copy_map[i][j] && !visit[i][j])
			{
				++cnt;
				bfs(i, j);
			}
		}
	}
	ans = max(ans, cnt);
}

void copy(int index)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (map[i][j] <= index)
				copy_map[i][j] = 0;
			else
				copy_map[i][j] = 1;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
			max_val = max(max_val, map[i][j]);
			min_val = min(min_val, map[i][j]);
		}
	}

	for (int i = min_val; i <= max_val; i++)
	{
		for (int j = 0; j < N; j++)
			fill(visit[j], visit[j] + N, false);

		copy(i);
		func();
	}

	cout << ans;

	return 0;
}

eve8108 3년 전 1

1. 비가 내리지 않는 경우도 생각하는것 같습니다.

강수량이 0이라면 안전영역은 1이기 때문입니다.

2.최소높이부터 시작하게 된다면 모두 동일한 높이일때 안전영역은 0 이 됩니다.

예를들어 N = 2이고,

3 3

이라는 배열이 있다면, 강수량이 1이거나 2일경우는 안전영역의 개수가 1이 됩니다.

하지만 최소높이부터 시작하게 된다면 무조건 안전영역이 나오지 않게 되겠지요.

lsk4393 3년 전 1

반례를 보고 깨달았습니다...

자세한 설명 덕분에 빠르게 이해할 수 있었습니다.

정말 너무 감사드립니다 ^^ !!!

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

문제

문제

출처

ICPC

안전영역 질문드립니다.

lsk4393 3년 전 0

eve8108 3년 전 1

lsk4393 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말