백준 10026번: 적록색약

문제

[BOJ][C++] 백준 10026번: 적록색약
문제는 https://www.acmicpc.net/problem/10026를 클릭해서 볼 수 있다.

풀이

먼저 적록색약이 아닌 사람이 봤을 때의 구역의 수부터 구했다. 구역을 구하는 과정은 그림을 돌면서 처음 방문하는 노드를 찾아 dfs를 진행했다. 현재 방문한 노드에서 인접 노드 중 방문한 적이 없고, 현재 노드와 색이 같은 인접 노드로 이동했다.

적록색약인 사람이 봤을 때의 구역의 수를 구하기 전에 2가지를 바꿨다. 첫 번째는 적록색약인 사람은 R과 G가 구분되지 않기 때문에 R을 G로 바꿔 그림에서 둘의 차이를 없앴다. 그림을 바꿨기 때문에 구역의 수를 구하는 과정은 적록색약이 아닌 사람이 봤을 때의 구역의 수를 구하는 방법과 같다. 구역의 수를 구하는 코드는 get_section_count() 함수로 묶어 코드를 작성했다. 두 번째는 탐색을 다시 시작하기 위해 is_visited를 0으로 초기화했다.

공부

처음에는 그림을 바꾸고, is_visited를 초기화하는 부분까지 main 함수에 모두 작성했다. 그러다보니 main 함수의 길이가 길어졌다. 기능별로 함수로 묶으니 main 함수가 간결해지고 가독성이 좋아졌다.

문제를 맞추고 나서 다른 코드들을 보니 is_visited를 0으로 초기화할 때 <string.h>의 memset 함수를 사용하는 것을 알게 되었다. 간단히 memset 함수는 메모리의 내용을 원하는 값으로 지정할 수 있는 함수이다. 배열의 값을 0 또는 -1로 초기화할 때 사용할 수 있다. memset은 내부적으로 메모리를 채울 때 값을 unsigned char로 형변환하여 1 byte 단위로 채운다. 4 bytes인 int을 넣으면 원하는 값과 다른 값이 들어가게 된다. 운 좋게 0과 -1은 형변환을 해도 값이 변하지 않기 때문에 사용할 수 있다. (0은 00000000, -1은 11111111)

// memset 함수의 원형
void* memset( void* dest, int ch, std::size_t count );

// memset(포인터, 지정할 값, 메모리 크기)
memset(is_visited, 0, sizeof(is_visited));

코드

#include <iostream>
using namespace std;

void check_section(int x, int y);
int get_section_count();
void change_picture_for_red_green_blind();
void reset_is_visited();

int N;								// 주어진 그림 줄의 수
string picture[101];						// RGB 그림
int is_visited[100][100] = {0};					// 방문 여부 확인 

int dx[4] = {1, -1, 0, 0};					// 상하좌우 방향 이동
int dy[4] = {0, 0, 1, -1};

int main() {

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> picture[i];
	}
	
	// 적록색약이 아닌 사람이 봤을 때의 구역의 수
	cout << get_section_count() << " ";

	change_picture_for_red_green_blind();
	reset_is_visited();
	
	// 적록색약인 사람이 봤을 때의 구역의 수
	cout << get_section_count() << "\n";

	return 0;
}

void check_section(int x, int y) {				// dfs 이용
	is_visited[x][y] = 1;					// 방문처리

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

		if (nx < 0 || nx >= N || ny < 0 || ny >= N)
			continue;

		if (is_visited[nx][ny] == 0 && picture[nx][ny] == picture[x][y]) { 
			check_section(nx, ny);			// 인접한 다른 노드로 이동
		}
	}
}

int get_section_count() {
	int section_count = 0;					// 구역의 수

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (is_visited[i][j] == 0) {
				section_count++;		// 처음 방문한 곳이므로 구역의 수 추가
				check_section(i, j);
			}
		}
	}
	return section_count;
}

void change_picture_for_red_green_blind() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (picture[i][j] == 'R') {		// 빨강색과 초록색의 차이 없앤다.
				picture[i][j] = 'G';
			}
		}
	}
}

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

채점 결과