백준 10026번 - 적록색약

10026번: 적록색약 (acmicpc.net)

크기가 N x N인 그리드 안에서 구역이 몇개있는지 찾는 문제다.

근데 일반사람이 인식하는 구역과 'R'과 'G'가 똑같이 보이는 적록색약을 가진 사람이 보는 구역 둘 다 출력해야한다.

 

#include<iostream>
#include<stack>
#include<utility>
using namespace std;

string Grid[100];
bool Color[100][100];
bool NoColor[100][100];

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

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

	stack<pair<int, int>> S;

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> Grid[i];

	cnt = 0;
	//적록색약이 아닌사람 
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (Color[i][j] == 1) continue;

			cnt++;

			S.push({ i,j });
			Color[i][j] = 1;

			while (!S.empty())
			{
				auto cur = S.top(); S.pop();
				for (int k = 0; k < 4; k++)
				{
					int x = cur.first + dx[k];
					int y = cur.second + dy[k];

					if (x < 0 || y < 0 || x >= n || y >= n) continue;
					if (Color[x][y] == 1 || Grid[x][y] != Grid[i][j]) continue;

					Color[x][y] = 1;
					S.push({ x,y });
				}
			}
		}
	}

	cout << cnt<<' ';

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (Grid[i][j] == 'R') Grid[i][j] = 'G';


	cnt = 0;
	//적록색약인 사람
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (NoColor[i][j] == 1) continue;

			cnt++;

			S.push({ i,j });
			NoColor[i][j] = 1;

			while (!S.empty())
			{
				auto cur = S.top(); S.pop();
				for (int k = 0; k < 4; k++)
				{
					int x = cur.first + dx[k];
					int y = cur.second + dy[k];

					if (x < 0 || y < 0 || x >= n || y >= n) continue;
					if (NoColor[x][y] == 1 || Grid[x][y] != Grid[i][j]) continue;

					NoColor[x][y] = 1;
					S.push({ x,y });
				}
			}
		}
	}

	cout << cnt;
	

	return 0;
}

함수를 따로 만들기가 귀찮아서 다 적었는데 코드가 너무 길어졌다.

큐를 많이 사용해서 이번엔 스택을 이용해 DFS로 풀어봤다.

 

일단 DFS를 돌리며 적록색약이 아닌사람이 인식하는 구역을 구해주었다.

그리고 이중 for문을 돌며 Grid 변수 안에있는 'R'을 전부 G로 바꿔주고 DFS를 돌아서 적록색약인 사람이 인식하는 구역을 구해 출력했다.

 

다 짜고보니 코드가 너무 긴게 맘에 안들어서 남들이 짠 코드들도 훑어보고 다시 코드를 작성했다.

 

#include<iostream>
#include<stack>
#include<utility>
using namespace std;

string Grid[100];
bool vis[100][100];

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

int n;
int Color, NoColor;

void dfs(int i, int j)
{
	stack<pair<int, int>> S;
	S.push({ i,j });
	vis[i][j] = 1;
	while (!S.empty())
	{
		auto cur = S.top(); S.pop();
		for (int k = 0; k < 4; k++)
		{
			int x = cur.first + dx[k];
			int y = cur.second + dy[k];

			if (x < 0 || y < 0 || x >= n || y >= n) continue;
			if (vis[x][y] == 1 || Grid[x][y] != Grid[i][j]) continue;

			vis[x][y] = 1;
			S.push({ x,y });
		}
	}
}

int counting()
{
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
		{
			if (!vis[i][j])
			{
				cnt++;
				dfs(i, j);
			}
		}
	}

	return cnt;
}


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

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> Grid[i];

	//색약 x
	Color = counting();

	for (int i = 0; i < n; i++)
	{
		fill(vis[i], vis[i] + n, 0);
		for (int j = 0; j < n; j++)
			if (Grid[i][j] == 'R') Grid[i][j] = 'G';
	}

	NoColor = counting();

	cout << Color << ' ' << NoColor;

	return 0;
}

이번엔 함수를 미리 만들어두었다.

그리고 100x100짜리 배열을 2개 만들어두는것이 아니라 vis 배열 하나만 두고 첫번째 dfs를 돌리고나서 두번째 dfs를 돌리기전에 초기화를 해서 다시 사용했다.

 

코드가 훨씬 깔끔해진 느낌이다.