백준 10026번: 적록색약

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

 

1. 문제

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

 

 

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

 

키워드 - DFS

 

해당 영역에서 구할 수 있는 영역은 4 구역이다. R,G,B 기준 일반인이 구별하는 색상 이다.

 

적록색약인 사람은 G 를 못보기 때문에 G 영역을 R 로 치환하고 DFS 를 구한다. 

 

 

Source

 

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>

using namespace std;

#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
#define ll long long

/*
* @memory  - 2056 kb
* @time    - 0 ms
*/

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

int n;
int board[101][101];
bool visited[101][101];

void dfs(int x, int y, int data) {

    visited[x][y] = true;

    for (int i=0; i<4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];

        if (ax < 0 || ay < 0 || ax >= n || ay >= n) {
            continue;
        }

        if (visited[ax][ay]) {
            continue;
        }

        if (board[ax][ay] == data) {
            dfs(ax, ay, data);
        }
    }
}
int main() {

    cin.tie(0);
    std::ios::sync_with_stdio(false);

    cin >> n;

    for (int i=0; i<n; i++)    {
        string s; cin >> s;

        const int size = s.size();
        for(int j=0; j<n; j++) {
            if (s[j] == 'R') {
                board[i][j] = 1;
            }
            else if (s[j] == 'G') {
                board[i][j] = 2;
            }
            else  if (s[j] == 'B') {
                board[i][j] = 3;
            }
            
        }
    }

    int sol_r = 0;
    int sol_g = 0;
    int sol_b = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {

            if (board[i][j] == 1 && !visited[i][j]) {
                sol_r++;
                dfs(i, j, 1);
            }

            if (board[i][j] == 2 && !visited[i][j]) {
                sol_g++;
                dfs(i, j, 2);
            }

            if (board[i][j] == 3 && !visited[i][j]) {
                sol_b++;
                dfs(i, j, 3);
            }
        }
    }

    int sol_a = sol_r + sol_g + sol_b;
    
    memset(visited, 0, sizeof(visited));

    for (int i=0; i<n; i++)    {
        for(int j=0; j<n; j++) {
            if (board[i][j] == 1 || board[i][j] == 2) {
                board[i][j] = 1;
            }
        }
    }

    sol_g = 0;
    sol_b = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {

            if (board[i][j] == 1 && !visited[i][j]) {
                sol_g++;
                dfs(i, j, 1);
            }

            if (board[i][j] == 3 && !visited[i][j]) {
                sol_b++;
                dfs(i, j, 3);
            }
        }
    }

    int sol_aa = sol_g + sol_b;

    cout << sol_a << " " << sol_aa << CENDL;

    return 0;
}