백준 16234번 _ 인구 이동

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

1. 풀이방법

 

1) 모든 continent를 다 visit할때까지 dfs, dfs할때 중요한게 국경이 연결되어있는 point, average는 미리 저장, 계산해놓는다. (시간초과 때문에 미리 계산해놓는게 좋음)

 

2) 같이 저장된 point들의 continent값은 아까구한 average값으로 다 바꾼다.

 

3) 국경이 열리지 않을때까지 반복하며 세어준다. 

 

---

 

2. 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
vector<vector<int>> continent;
int N, L , R;
int visit[52][52];
vector<vector<pair<int, int>>> Point;

void visitInit()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			visit[i][j] = 0;
}

bool openPossible(int here, int there)
{
	if (abs(here - there) >= L && abs(here - there) <= R)
		return true;
	return false;
}

int dfsCnt = 0;
int dfsSum = 0;
vector<pair<int, int>> PointTmp;
void dfs(int hy, int hx, int checkNumber)
{
	PointTmp.push_back({ hy, hx });
	dfsSum += continent[hy][hx];
	dfsCnt++;
	visit[hy][hx] = checkNumber;
	//우하좌상 탐색
	if (hx + 1 < N)
		if (visit[hy][hx + 1] == 0)
			if (openPossible(continent[hy][hx], continent[hy][hx + 1]))
				dfs(hy, hx + 1, checkNumber);
	if (hy + 1 < N)
		if (visit[hy + 1][hx] == 0)
			if (openPossible(continent[hy][hx], continent[hy + 1][hx]))
				dfs(hy + 1, hx, checkNumber);
	if (hx - 1 >= 0)
		if (visit[hy][hx - 1] == 0)
			if (openPossible(continent[hy][hx], continent[hy][hx - 1]))
				dfs(hy, hx - 1, checkNumber);
	if(hy -1 >=0)
		if (visit[hy - 1][hx] == 0)
			if(openPossible(continent[hy][hx], continent[hy-1][hx]))
				dfs(hy - 1, hx, checkNumber);

	
}

map<int, int> CheckNumAndAverage;
void drawNewcontinent(int checkNumber)
{
	//changecontinent는 그리 필요하지 않은 변수이고 그냥 continent에 직접적으로 그려도 무방 
	vector<vector<int>> changecontinent = continent;
	for (int c = 1; c < checkNumber; c++)
	{
		int average = CheckNumAndAverage[c];
		for (auto& point : Point[c-1])
		{
			changecontinent[point.first][point.second] = average;
		}
	}
	continent = move(changecontinent);
}


int Open()
{
	int openCnt = 0;
	while (1)
	{
		int cnt = 1;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (visit[i][j] == 0)
				{
					dfsCnt = 0;
					dfsSum = 0;
					dfs(i, j, cnt);
					CheckNumAndAverage[cnt] = dfsSum / dfsCnt;
					Point.push_back(move(PointTmp));		
					cnt++;
				}
			}
		}
		//인구이동이 더이상 일어나지 않을때
		if (cnt - 1 == N * N)
			break;
		//draw
		drawNewcontinent(cnt);
		//visit 초기화
		visitInit();
		Point.clear();
		openCnt++;
	}
	return openCnt;
}

int main()
{
	cin >> N >> L >> R;
	continent.resize(N + 2);
	for (int i = 0; i < N; i++)
		continent[i].resize(N + 2);

	int value;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> value;
			continent[i][j] = value;
		}
	}

	//탐색
	int answer = Open();

	cout << answer;

	return 0;
}

 

---

 

3. 후기

 

 처음에 짰던 코드가 average, point값들을 미리계산을 안해 똑같은 continent값을 계속 반복하는 식으로 코드가 짜여져서 시간초과가 났었다. 그 부분을 고치면서 풀어가다보니 코드가 조금 명확하지 않은면도 있다. 

 이 문제는 다시한번 깔끔히 풀어봐야겠다.