백준 10026 - 적록색약

문제링크

• 백준 10026

문제 설명

• NxN 칸에 R, G, B 중 하나가 적혀있다. 같은 색상이 상하좌우로 인접해 있는 경우 두 글자는 같은 구역에 속한다.
• 같은 색상끼리 묶어서 하나의 구역이 된다. 적록색약인 경우 R과 G는 같은 색상이다.
• 적록색약인 사람과 아닌 사람이 봤을 때 구역의 수를 각각 구하라

문제 접근 방향(bokyoung) — 메모리 초과

• 적록색약인 사람의 map과 적록색약이 아닌 사람의 map을 따로 만든다.
• NxN 전체 칸을 탐색해야한다.
  1. 구역이 정해지지 않은 칸의 좌표를 찾는다. - 이 부분이 실행된 횟수가 구역의 수 1-1. 해당 좌표로 상하좌우를 탐색한다. 1-2. 같은 색상이라면 이동하고 구역 표시를 한다.
• 더이상 같은 구역으로 만들 칸이 없다면 1로 돌아간다.

원인 분석

• 메모리 초과가 발생하는 이유는.. 스택 오버플로우의 경우가 많다.
  1. 너무 많은 변수들을 배열 등에 저장했는가?
  • N은 최대 100까지 가능한데, 100x100 2차원 배열을 총 2개 만들었다.
    1. DFS 등에서 재귀적 호출을 통해 너무 많은 함수가 호출되는가?

구현 결과 (메모리 초과 발생)

#include <iostream>
#include <vector>
#include <string>
#include <cctype>
using namespace std;

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

// 유효한 좌표인지 확인한다.
bool check_valid(int xpos, int ypos)
{
	if (xpos >= 0 && xpos < N && ypos >= 0 && ypos < N)
		return true;
	else
		return false;
}

void set_area(vector<string>& map, int xpos, int ypos, char color, int cnt)
{
	cnt_recur++;
	// 기저사례: 이동한 좌표의 색상이 같지 않은 경우
	if (color != map[xpos][ypos]) return;

	// 상하좌우 4가지 방향으로 이동하며 재귀호출을 통한 완전탐색
	for (int dir = 0; dir < 4; dir++)
	{
		map[xpos][ypos] = cnt + '0'; // 구역 번호 설정
		int next_x = xpos + dx[dir];
		int next_y = ypos + dy[dir];

		// 지도를 벗어나는 좌표의 경우 스킵
		if (check_valid(next_x, next_y) == false) continue;
		// 구역이 정해진 칸은 스킵
		if (!isalpha(map[next_x][next_y])) continue;

		set_area(map, next_x, next_y, color, cnt);
	}
	return;
}

void find_num_area(vector<string>& normal_map, vector<string>& weak_color_map)
{
	int normal_cnt = 0;
	int weak_color_cnt = 0;

	// 칸에 적힌 문자가 알파벳 문자(R,G,B)이면 구역을 만들기 위해 set_area 함수를 호출하고,
	// 칸에 적힌 문자가 숫자 문자(1, 2, ...) 이면 구역이 정해졌으므로 아무것도 하지 않는다.
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			if (isalpha(normal_map[r][c]))
			{
				normal_cnt++;
				set_area(normal_map, r, c, normal_map[r][c], normal_cnt);
			}
			if (isalpha(weak_color_map[r][c]))
			{
				weak_color_cnt++;
				set_area(weak_color_map, r, c, weak_color_map[r][c], weak_color_cnt);
			}
		}
	}

	cout << normal_cnt << " " << weak_color_cnt << endl;
}

void print_map(vector<string>& map1, vector<string>& map2)
{
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			cout << map1[r][c];
		}
		cout << endl;
	}
	cout << "----------------------------" << endl;
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			cout << map2[r][c];
		}
		cout << endl;
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N;

	vector<string> normal_map(N);
	vector<string> weak_color_map(N);
	string str;
	for (int line = 0; line < N; line++)
	{
		cin >> str;
		normal_map[line] = str;
		for (int i = 0; i < str.length(); i++)
		{
			if (str[i] == 'G') // 색약이 있는 경우 R과 G는 같은 색이다.
				str[i] = 'R';
		}
		weak_color_map[line] = str; // 색약이 있는 사람이 보는 맵
	}

	find_num_area(normal_map, weak_color_map);
	// print_map(normal_map, weak_color_map);
	cout << cnt_recur << endl;
	return 0;
}

개선 사항

• 재귀함수 호출 전에 이동할 좌표의 유효성을 판단하여 재귀함수 호출을 최소한으로 줄인다.
• 2차원 배열 2개를 만드는 것이 메모리 초과를 일으켰다고 생각하지 않았다. 왜냐하면, 다른 통과된 답안을 보니 방문표시를 위한 vixited[100][100] 배열을 선언하여도 문제가 없었기 때문이다.
• 구역이 정해진 칸은 R,G,B 문자가 아닌 1,2,3.. 와 같이 숫자문자로 나타내고 있었는데, 구역이 10개 이상으로 나누어지면 두 자리 숫자 문자를 칸에 나타낼 수 없는 현상을 찾아냈다.
• ‘0’ 아스키코드 값은 80인데, char형은 최대 127까지만 값을 가질 수 있기 때문에, 구역이 47개가 넘어가는 순간 오버플로우가 발생한다. 따라서, 메모리 초과 원인은 프로그램 전체의 스택 오버플로우가 아닌, 자료형에 따른 오버플로우 현상에 의한 것으로 판단되었다.

구현 결과

#include <iostream>
#include <vector>
#include <string>
#include <cctype>
using namespace std;

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

// 유효한 좌표인지 확인한다.
bool check_valid(int xpos, int ypos)
{
	if (xpos >= 0 && xpos < N && ypos >= 0 && ypos < N)
		return true;
	else
		return false;
}

void set_area(vector<string>& map, int xpos, int ypos, char color)
{
	// 상하좌우 4가지 방향으로 이동하며 재귀호출을 통한 완전탐색
	for (int dir = 0; dir < 4; dir++)
	{
		map[xpos][ypos] = '*'; // 구역 번호 설정
		int next_x = xpos + dx[dir];
		int next_y = ypos + dy[dir];

		// 지도를 벗어나는 좌표의 경우 스킵
		if (check_valid(next_x, next_y) == false) continue;
		// 구역이 정해진 칸은 스킵
		if (!isalpha(map[next_x][next_y])) continue;
		// 이동한 좌표의 색상이 다른 경우 스킵
		if (color != map[next_x][next_y]) continue;
		set_area(map, next_x, next_y, color);
	}
	return;
}

void find_num_area(vector<string>& normal_map, vector<string>& weak_color_map)
{
	int normal_cnt = 0;
	int weak_color_cnt = 0;

	// 칸에 적힌 문자가 알파벳 문자(R,G,B)이면 구역을 만들기 위해 set_area 함수를 호출하고,
	// 칸에 적힌 문자가 숫자 문자(1, 2, ...) 이면 구역이 정해졌으므로 아무것도 하지 않는다.
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			if (isalpha(normal_map[r][c]))
			{
				normal_cnt++;
				set_area(normal_map, r, c, normal_map[r][c]);
			}
			if (isalpha(weak_color_map[r][c]))
			{
				weak_color_cnt++;
				set_area(weak_color_map, r, c, weak_color_map[r][c]);
			}
		}
	}

	cout << normal_cnt << " " << weak_color_cnt << endl;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N;

	vector<string> normal_map(N);
	vector<string> weak_color_map(N);
	string str;
	for (int line = 0; line < N; line++)
	{
		cin >> str;
		normal_map[line] = str;
		for (int i = 0; i < str.length(); i++)
		{
			if (str[i] == 'G') // 색약이 있는 경우 R과 G는 같은 색이다.
				str[i] = 'R';
		}
		weak_color_map[line] = str; // 색약이 있는 사람이 보는 맵
	}

	find_num_area(normal_map, weak_color_map);
	return 0;
}