글 읽기 - 반례를 못찾겠습니다..

inhadong 3년 전 0

주어진 예제와 질문 검색에 있는 테스트케이스는 통과를 하는데

꽤 오랜 시간 고민했는데 반례를 못찾겠네요...

왜 틀렸는지 알려주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;

int n;
int l;
int r;
int arr[51][51];
bool visited[51][51];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
queue<pair<int, int>> q;
vector<pair<int, int>> v[2001]; //인구이동이 일어나는 덩어리의 좌표를 보관하기 위한 벡터
vector<int> check; //인구이동이 일어나는지 안일어나는지 확인하기 위한 벡터
int area;
int answer;

void init()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			visited[i][j] = false;
		}
	}
}

void print()
{
	cout << "########################" << endl;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
}

void bfs(int x, int y)
{
	visited[x][y] = true;
	area++;
	q.push(make_pair(x, y));
	while (!q.empty())
	{
		int fx = q.front().first;
		int fy = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++)
		{
			int nx = fx + dx[k];
			int ny = fy + dy[k];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n)
			{
				continue;
			}
			if ( abs(arr[nx][ny] - arr[fx][fy]) >= l && abs(arr[nx][ny] - arr[fx][fy]) <= r && visited[nx][ny] == false)
			{
				q.push(make_pair(nx, ny));
				visited[nx][ny] = true;
				area++;
			}
		}
	}
}

int main()
{
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
		}
	}

	bool gameover = false; //더이상 인구이동이 있는지 없는지 확인하는 변수
	while (true)
	{
		int cnt = 0; //인구이동이 일어나는 좌표들을 저장하기위한 벡터의 row 인덱스
		check.clear();
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				init(); //visited배열 초기화
				area = 0;
				bfs(i, j); //bfs
				if (area == 1) //area가 1이라면 인접한 지역에는 인구이동이 일어나지 않음
				{
					check.push_back(area);
					if (check.size() == n * n) //check의 size가 n*n이라면 모든 map의 모든 요소에 인구이동이 이루어지지 않았음
					{
						gameover = true;
					}
					continue;
				}
				else
				{
					//bfs순회 후 인구 이동이 일어난 component의 좌표들을 저장한다.
					for (int k = 0; k < n; k++)
					{
						for (int l = 0; l < n; l++)
						{
							if (visited[k][l] == true)
							{
								v[cnt].push_back(make_pair(k, l));
							}
						}
					}
					cnt++;//row index를 증가
				}
			}
		}

		for (int i = 0; i < 51; i++)
		{
			if (v[i].size() == 0)
			{
				continue;
			}
			else
			{
				//인구이동이 일어난 component끼리 주어진 연산을 수행한다.
				int people = 0;
				for (int j = 0; j < v[i].size(); j++)
				{
					people = people + arr[v[i][j].first][v[i][j].second];
				}
				people = people / v[i].size();

				for (int j = 0; j < v[i].size(); j++)
				{
					arr[v[i][j].first][v[i][j].second] = people;
				}
			}
		}
		
		//연산 수행 후 초기화
		for (int i = 0; i < 51; i++)
		{
			if (v[i].size() == 0)
			{
				continue;
			}
			else
			{
				v[i].clear();
			}
		}
		if (gameover == true)
		{
			break;
		}
		//print();
		answer++;
	}
	cout << answer << endl;
	return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다..

inhadong 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말