백준 10026번: 적록색약

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

10026번: 적록색약

 

 

0. 알고리즘 분류

 그래피 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

1. 문제

 

 

2. 풀이

 문제 자체는 일반 DFS/BFS 문제이다. 적록색약은 그냥 주어진 입력에서 G를 R로 바꿔주기만 하면 된다. 다만 시간 제한이 1초라서, 반복문을 사용하는데에 생각을 해봐야한다. 

 

 inArea() 함수는 입력으로 들어온 좌표 x, y 가 배열의 범위에 들어있는지 체크하는 함수이다. bfs() 함수는 일반 bfs함수를 살짝 변형한 것이다. 첫 번째 탐색은 정상인, 두 번째 탐색은 적록색약을 가진 사람의 경우이다. 첫 번째 bfs 탐색을 돌릴 때, 현재 위치의 색이 G이면, R로 바꿔주도록 했다. 어차피 이미 해당 좌표는 방문을 완료했기에 색깔을 바꿔도 첫 번째 탐색에는 별 영향이 없기에, 두 번째 탐색의 편의를 위해 해주었다.

 

 쉬운 문제였지만, 과다한 배열 사용으로 메모리 초과와 반복문 중첩으로 시간제한에 꽤나 골머리를 앓았다. 어찌저찌 풀었지만, 뭐가 문제였는지 정확하게 모르겠다. 아마 사소한 메모리 사용과 조건문/반복문이 겹쳐서 그런 것 같다.

 

 

3. 코드

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

int n;
char a[100][100];
bool visited[100][100];
int dir_x[4] = {1,-1,0,0};
int dir_y[4] = {0,0,1,-1};

bool inArea(int x, int y) {
	if (0 <= x && x < n && 0 <= y && y < n)
		return true;
	
	return false;
}

void bfs(int x, int y) {
	char color = a[x][y];
	
	queue<pair<int,int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = true;
	while (!q.empty()) {
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();
		
		if (a[cur_x][cur_y] == 'G') a[cur_x][cur_y] = 'R';
		
		for (int i = 0; i < 4; i++) {
			int next_x = cur_x + dir_x[i];
			int next_y = cur_y + dir_y[i];
			
			if (inArea(cur_x + dir_x[i], cur_y + dir_y[i])) {
				if (!visited[next_x][next_y]) {
					if (color == a[next_x][next_y]) {
						q.push(make_pair(next_x, next_y));
						visited[next_x][next_y] = true;
					}
				}
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	
	int ans1 = 0;
	int ans2 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				bfs(i, j);
				ans1++;
			}
		}
	}
	
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				bfs(i, j);
				ans2++;
			}
		}
	}
	
	cout << ans1 << ' ' << ans2;
	
	return 0;
}