ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 10026 적록색약 (C++)

Posted on Mar 2, 2021 #DFS/BFS   #Algorithm  

10026 | 적록색약

🙋‍♀️ 문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

🙌 입출력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

🙋‍♂️ 예제 입출력

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

4 3

🚀 코드

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;

vector<vector<char>> v(101, vector<char>(101));
vector<vector<char>> blind(101, vector<char>(101));
int visit[101][101] = { 0 };
int visit2[101][101] = { 0 };
int n = 0;
int cnt = 0;
int cnt2 = 0;

void rDfs(char color, int i, int j) {
	if (i < 0 || i >= n || j < 0 || j >= n) {
		return;
	}
	if (v[i][j] == color && visit[i][j] != 1) {
		visit[i][j] = 1;
		cnt++;
		rDfs(color, i - 1, j);
		rDfs(color, i + 1, j);
		rDfs(color, i, j - 1);
		rDfs(color, i, j + 1);
	}
}

void rDfs2(char color, int i, int j) {
	if (i < 0 || i >= n || j < 0 || j >= n) {
		return;
	}
	if (blind[i][j] == color && visit2[i][j] != 1) {
		visit2[i][j] = 1;
		cnt2++;
		rDfs2(color, i - 1, j);
		rDfs2(color, i + 1, j);
		rDfs2(color, i, j - 1);
		rDfs2(color, i, j + 1);
	}
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
			if (v[i][j] == 'G') {
				blind[i][j] = 'R';
			}
			else {
				blind[i][j] = v[i][j];
			}
		}
	}
	int sector = 0;
	int sector2 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			rDfs('R', i, j);
			if (cnt > 0) {
				sector++;
			}
			rDfs2('R', i, j);
			if (cnt2 > 0) {
				sector2++;
			}
			cnt = 0;
			cnt2 = 0;
			rDfs('G', i, j);
			if (cnt > 0) {
				sector++;
			}
			cnt = 0;
			rDfs('B', i, j);
			if (cnt > 0) {
				sector++;
			}
			rDfs2('B', i, j);
			if (cnt2 > 0) {
				sector2++;
			}
			cnt = 0;
			cnt2 = 0;
		}
	}
	cout << sector << ' ' << sector2;

	return 0;
}

🌠 메모

이제 DFS문제는 쉽게 풀어낼 수 있게 된 거 같다. 기본 로직이 거의 응용이 되지 않고 그대로 구현만 하면 되어서 섹션 구별만 문제에 따라서 잘 해주면 된다.

색상을 저장하는 배열을 전역으로 선언하고 사용해서 같은 내용의 함수를 두번이나 적게 되었다. 이부분을 좀 깔끔하게 하고 싶긴 하다.. 배열을 인자로 넘기면 함수를 두개 만들지 않아도 될거 같은데 그러면 혹시 시간이 많이 걸릴까봐 이렇게 코드를 짜게 되었다.

변수만 적절히 초기화를 잘 해주면 금방 풀리는 문제다. 적록색약의 경우에는 'G'를 'R'로 바꾸어 배열에 저장하고 똑같이 탐색을 해주었다.



# 카테고리