뚝딱뚝딱

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

💡 적록색약

✅ 문제 풀이

• 골드 치고 쉬운 dfs 문제
• 보자마자 어떻게 풀어야 할지 접근방식이 바로 보이는 문제!!
• 주의해야 할 점은 적록색약일 경우 R,G가 인접해있으면 같은 영역으로 본다는 점
• 이런 영역 문제를 풀 때는 방문한 칸에 대해서는 방문 표시를 하기때문에, 두 가지 접근 방식에 대해서 서로 영향을 받지 않기 위해서 arr를 두개를 만들고 시작했다.
• arr1은 적록색약이 아닌 사람이 보는 영역으로, R은 1, G는2, B는3 을 저장했다.
• arr2는 적록색약인 사람이 보는 영역으로, R과 G는 1, B는 3을 저장했다. 이게 핵심이다. R과 G를 같은 값으로 배정하여 같은 영역으로 인식되도록 하였다.
• 방문한 것에 대해서는 arr 값을 0으로 갱신하도록 하며, 방문 여부를 체크했다.
• arr 크기만큼 순회하면서 각 칸이 0이 아니면 dfs 함수를 호출하여, 현재 위치와 현재 위치의 값, 그리고 참조할 arr를 인자로 넘겨주었다.
• arr1과 arr2에 대해서 각각 취해야 하기 때문에 두번 씩 호출해 주었다.

• dfs 함수 내 동작
• 현재 칸을 방문했으므로 값을 0으로 갱신해준다.
• 현재 칸을 기준으로 상하좌우가 arr의 범위내에 있고, 현재 칸과 값이 동일하면 같은 영역이므로 해당 칸에 대해서 DFS를 재귀호출하여 한 영역에 대해 계속 탐색하도록 하였다.

• 다시 돌아와서, main의 2중 for문에서 dfs가 호출되었다는 것은 영역의 시작과 같은 의미이므로, dfs를 호출한 후에는 answer을 증가시켜 영역을 개수를 카운트 하였다.
• 이때 적록색약이 아닌 경우는 answer1을, 적록색약인 경우는 answer2를 카운트 하도록 하였다.
• 최종 answer들을 출력한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int n;
vector<vector<int>> arr1;
vector<vector<int>> arr2;

int answer1 = 0;
int answer2 = 0;

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

void dfs(int i, int j, int num, vector<vector<int>> &arr) {
	arr[i][j] = 0;
	
	for (int k = 0; k < 4; k++) {
		int x = i + dx[k];
		int y = j + dy[k];
		if (x >= 0 && x < n&&y >= 0 && y < n&&arr[x][y] == num) {
			dfs(x, y, num, arr);
		}
	}
}

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

	cin >> n;

	arr1.resize(n, vector<int>(n));
	arr2.resize(n, vector<int>(n));

	string str;
	for (int i = 0; i < n; i++) {
		cin >> str;
		for (int j = 0; j < n; j++) {
			if (str[j] == 'R') {
				arr1[i][j] = 1;
				arr2[i][j] = 1;
			}
			else if (str[j] == 'G') {
				arr1[i][j] = 2;
				arr2[i][j] = 1;
			}
			else {
				arr1[i][j] = 3;
				arr2[i][j] = 3;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr1[i][j] != 0) {
				dfs(i, j, arr1[i][j], arr1);
				answer1++;
			}
			if (arr2[i][j] != 0) {
				dfs(i, j, arr2[i][j], arr2);
				answer2++;
			}
		}
	}
	
	cout << answer1 << " " << answer2;

	return 0;
}