[코딩테스트 C++] 적록색약

오늘의 문제

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

적록색약

접근 방법

• 구역의 개수를 찾는 전형적인 그래프 탐색 문제이나, R과 G를 구분하지 않는 재미있는 요소가 들어있다.
• R 혹은 G인 경우에는 R또는 G인경우 모두를 같이 탐색, B인 경우에는 B인 것만 탐색한다.
• dfs함수를 두개 만들까 하다가 배열 포인터를 사용해서 이중 포문 안에서, 두가지를 한번에 연산하도록 했다.

나의 풀이

#include<iostream>
using namespace std;
int n;
string s;
const int MAX = 100;
char arr[MAX][MAX];
char arr2[MAX][MAX];
int dx[] ={0, 0, -1, 1};
int dy[] ={1, -1, 0, 0};

void dfs(int y, int x, bool type, char(*arr)[MAX]){
    char c = arr[y][x];
        arr[y][x] = 'C';
    for(int i=0;i<4;i++){
        int mx = x + dx[i];
        int my = y + dy[i];
        if(mx >= n || mx<0 || my >= n || my<0)
            continue;
        if(type == true && (c == 'R' || c == 'G')){
            if(arr[my][mx] == 'R' || arr[my][mx] == 'G')
                dfs(my, mx, type, arr);
        }else{
            if(arr[my][mx] == c)
                dfs(my, mx, type, arr);
        }
    }
}

void solution(){
    int answer =0;
    int answer2 =0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(arr[i][j] != 'C'){
                dfs(i, j, false, arr);
                answer++;
            }
            if(arr2[i][j] != 'C'){
                dfs(i, j, true, arr2);
                answer2++;
            }
        }
    }
    printf("%d %d\n", answer, answer2);
}

다른 풀이

#include<cstdio>
#include<cstring>

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

int n;
char map[101][101], nap[101][101];

void dfs(int y, int x, char c, bool sw) {
	sw ? nap[y][x] = 0 : map[y][x] = 0;
	for (int w = 0; w < 4; ++w) {
		int ny = y + dy[w], nx = x + dx[w];
		if (ny < 0 || nx < 0 || ny == n || nx == n) continue;
		if (!sw) {
			if (map[ny][nx] == c) dfs(ny, nx, c, sw);
		}
		else {
			if( nap[ny][nx] == c || (c == 'R' && nap[ny][nx] == 'G')
				|| (c == 'G' && nap[ny][nx] == 'R')) dfs(ny, nx, c, sw);
		}
	}
}
void component() {
	int np = 0, mp = 0;
	for (int i = 0; i < n; ++i)
		strcpy(nap[i], map[i]);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (map[i][j]) mp++, dfs(i, j, map[i][j], 0);
			if (nap[i][j]) np++, dfs(i, j, nap[i][j], 1);
		}
	}
	printf("%d %d", mp, np);
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf(" %s", map[i]);
	component();
}

배울 점

• 기본 로직은 같은데 arr를 탐색하는 과정에서 bool 만을 이용해 구분했다 오호~