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

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

문제 설명

n*n 크기의 배열이 주어진다.

각 배열의 칸에는 R,G,B 중 하나의 값이 들어가 있는데, 적록 색약인 경우에는 R과 G를 구분하지 못해 한 색으로 본다. 

가로 세로로 연결된 같은 색끼리 모여있는 것들이 적록색약과 적록색약이 아닌 사람이 봤을때 몇개인지 개수를 출력하는 문제이다.

 

주요 로직

1. 그래프 탐색 문제이다

dfs로 같은 색이면 계속해서 탐색하도록 코드를 구성했다

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n;
string str;
int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};
int arr[104][104], brr[104][104], visited[104][104];

void dfs(int y, int x, int p){
	visited[y][x] = 1;
	for(int i=0; i<4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
		if(visited[ny][nx]) continue;
		if(p == 0){ // 적록 색약 아님 -> arr 
			if(arr[ny][nx] != arr[y][x]) continue;
			dfs(ny, nx, p); 
		}
		else if(p == 1){
			if(brr[ny][nx] != brr[y][x]) continue;
			dfs(ny, nx, p);
		}
	}
}

int go(int k){
	fill(&visited[0][0], &visited[0][0]+104*104, 0);
	int cnt = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(visited[i][j]) continue;
			dfs(i,j,k);
			cnt++;
		}
	}
	return cnt;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> str;
		for(int j=0; j<n; j++){
			if(str[j] == 'R') arr[i][j] = 1, brr[i][j] = 1;
			else if(str[j] == 'G') arr[i][j] = 2, brr[i][j] = 1;
			else if(str[j] == 'B') arr[i][j] = 3, brr[i][j] = 3;
		}
	}
	
	cout << go(0) << "\n"; // 적록 색약 
	cout << go(1); // 적록 색약 아님 
	
	return 0;
}