포스트

백준 10026. 적록색약

게시
https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/images/boj-og.png
https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/images/boj-og.png
By Dukgukim

알고리즘 중급 문제 중 611 - BFS (연습)

적록색약

1. 간단 설명

image

맵 정보가 주어지는데, 적록색맹인 사람은 R-G를 구분을 못한다

이러한 예시가 주어졌을 때, 일반인과 적록색약 입장에서 구역이 몇개 있는지 구하는 문제

2. 예시

1
2
3
4
5

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

일반인 입장에서는 4개가 있지만

적록색약 입장에서는

1
2
3
4
5

RRRBB
RRBBB
BBBRR
BBRRR
RRRRR

처럼 보이므로 3개로 보인다

3. 알고리즘

처음 생각한 알고리즘은 다음과 같다

1
2
3
4
5
6
7

1. 맵 정보를 입력받고
2. G를 R로 저장한 색맹용 맵을 하나 더 만든다
3. 일반인용 맵에서 BFS를 통해 (0,0)부터 (N-1, N-1)까지 탐색을 통해 
   해당 그리드와 연결된 그리드를 지운다. 
   - 해당 BFS가 호출된 회수가 영역의 개수임
4. 마찬가지로 색맹용 맵에서도 (0,0)부터 (N-1,N-1)까지 탐색을 통해 영역의 개수를 구한다
5. 둘을 출력한다

간단히 맵 두개를 놓고, BFS함수를 버전에 맞게 호출하여 체크하는 방법이다

그러나 이 방법은 맵 두개를 쓰므로 맵이 커질수록 메모리 사용량이 많을 것 같다고 판단하여

맵 하나로 BFS를 돌리는 방법을 생각해보았다

1
2
3
4
5
6
7
8
9
10

1. 맵 정보 입력받기
2. 일반인 버전으로 (0,0)에서 (N-1,N-1)까지 탐색 한다
	2-1. 만약 방문하지 않았던 곳이라면, 현재 색상과 좌표를 BFS를 통해 탐색한다
	2-2. 이 색상과 같은 색상들을 찾아 모두 방문처리한다
	2-3. BFS 탐색이 끝났다면 구역 개수를 1 증가시킨다
	2-4. 구역 개수를 리턴
3. 색맹 버전으로 마찬가지로 탐색
	3-1. 같은 방식으로 진행하되, R과 G를 동일하게 처리한다
	3-2. 구역 개수를 리턴
4. 일반인 버전 구역과 색맹 버전 구역 개수를 각각 출력 후 종료

4. 소스코드

맵 하나를 사용하는 버전

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <iostream>
#include <queue>
#include <string>

#define MAX 101

using namespace std;

int N;
string map[MAX], colorblind_map[MAX];
bool visited[MAX][MAX];

int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };

void Input() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}
}

void BFS(int yy, int xx, bool isColorBlind) {
	queue<pair<int, int>> qu;
	visited[yy][xx] = 1;
	qu.push({ yy, xx });

	char currentColor = map[yy][xx];
	
	while (!qu.empty()) {
		pair<int, int> now = qu.front();
		qu.pop();

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.first;
			int dx = direct[t][1] + now.second;

			if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue;
			if (visited[dy][dx] == true) continue;
			
			// 색맹인 경우, R과 G를 동일하게 처리한다
			if (isColorBlind) {
				if ((currentColor == 'R' || currentColor == 'G') &&
					(map[dy][dx] == 'R' || map[dy][dx] == 'G')) {
					visited[dy][dx] = true;
					qu.push({ dy, dx });
				}
				else if(map[dy][dx] == currentColor){
					visited[dy][dx] = true;
					qu.push({ dy, dx });
				}
			}
			else {
				if (map[dy][dx] == currentColor) {
					visited[dy][dx] = true;
					qu.push({ dy, dx });
				}
			}
		}
	}
}

int CountAreas(bool isColorBlind) {
	memset(visited, 0, sizeof(visited));
	int areaCount = 0;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (!visited[y][x]) {
				BFS(y, x, isColorBlind);
				areaCount++;
			}
		}
	}
	return areaCount;
}

int main() {
	Input();

	int normal_area = CountAreas(false);     // 일반인 기준 구역 수
	int color_blind_area = CountAreas(true); // 색맹 기준 구역 수

	cout << normal_area << " " << color_blind_area;
	return 0;
}

맵 두개를 운용하는 버전

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include <iostream>
#include <queue>
#include <string>

#define MAX 101

using namespace std;

int N;
string map[MAX], colorblind_map[MAX];
bool visited[MAX][MAX];

int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 'R') {
				colorblind_map[y].push_back('G');
			}
			else {
				colorblind_map[y].push_back(map[y][x]); // char to string
			}
		}
	}
}

void BFS(int mode, int yy, int xx, char ch) {
	memset(visited, 0, sizeof(visited));
	queue<pair<int, int>> qu;

	if (mode == 0) {
		map[yy][xx] = '.';
	}
	else if (mode == 1) {
		colorblind_map[yy][xx] = '.';
	}
	
	visited[yy][xx] = 1;
	qu.push({ yy, xx });

	while (!qu.empty()) {
		pair<int, int> now = qu.front();
		qu.pop();

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.first;
			int dx = direct[t][1] + now.second;

			if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue;
			if (visited[dy][dx] == true) continue;
			
			if (mode == 0) {
				if (map[dy][dx] != ch) continue;
			}
			else if (mode == 1) {
				if (colorblind_map[dy][dx] != ch) continue;
			}
			
			visited[dy][dx] = 1;
			if (mode == 0) {
				map[dy][dx] = '.';
			}
			else if (mode == 1) {
				colorblind_map[dy][dx] = '.';
			}
			qu.push({ dy,dx });
			
		}
	}
}

int main() {
	Input();

	int normal_area = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] != '.') {
				BFS(0, y, x, map[y][x]);
				normal_area++;
			}
		}
	}

	int color_blind_area = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (colorblind_map[y][x] != '.') {
				BFS(1, y, x, colorblind_map[y][x]);
				color_blind_area++;
			}
		}
	}

	cout << normal_area << " " << color_blind_area;
	return 0;
}
Algorithm, Problem Solving
graph search bfs dfs
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.