[백준/C,C++] 10026번: 적록색약

www.acmicpc.net/problem/10026

10026번: 적록색약

풀이

hackids.tistory.com/77

[백준/C,C++] 2667번: 단지번호붙이기

2667번: 단지번호붙이기와 마찬가지로 한 정점에서 모든 정점으로 이동이 불가능하기 때문에,

 

모든 정점을 방문할 때까지 BFS를 실행시켜줘야 하는 문제입니다.

 

#include<iostream>
#include<queue>
#include<cstring>

#define py first
#define px second

using namespace std;

using PAIR = pair<int, int>;

const int MAX = 100;

int n;
string s[MAX];
bool visited[MAX][MAX];
queue<PAIR> q;
PAIR d[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
int res;

void visit(int y, int x)
{
    visited[y][x] = true;
    q.push(pair(y, x));
}

void search()
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                visit(i, j);
                while (!q.empty()) {
                    PAIR node = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++) {
                        int ny = node.py + d[k].py;
                        int nx = node.px + d[k].px;
                        if (ny >= 0 && nx >= 0 && ny < n && nx < n) {
                            if (!visited[ny][nx] && s[i][j] == s[ny][nx]) visit(ny, nx);
                        }
                    }
                }
                res++;
            }
        }
    }
}

int main(void)
{
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    search();
    cout << res << ' ';

    memset(visited, false, sizeof(visited));
    res = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == 'G') s[i][j] = 'R';
        }
    }

    search();
    cout << res;

    return 0;
}

반례

Input

6
RRRRRB
RRRRBB
RRGBBB
RRRRBB
RBBGGG
BbGGGG

Output

7 5