백준 10026 적록색약 (C++)

안유태·2022년 8월 22일
0

알고리즘

목록 보기
25/239

10026번: 적록색약

BFS를 이용한 간단한 문제이다. 문제에서 구해야하는 답은 적록색약이 아닌 사람과 적록색약인 사람이 봤을 때의 구역의 수이다. 그렇기에 BFSBFS2 함수 두가지를 사용하여 답을 구하였다. BFS2 함수는 적록색약을 대상으로하는 함수이기때문에 처음 배열을 입력받을 때 G 구역을 R로 바꿔준 문자열 B를 사용하여 BFS를 돌려주었다. 두 함수 모두 방문한 구역은 'E'로 바꿔주어 visit배열 없이 방문 여부를 확인해 주었다.
간단한 문제였기에 큰 어려움이 없었다.



#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int N;
string A[100];
string B[100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

void bfs(int a, int b, char c) {
    queue<pair<int, int>> q;

    A[a][b] = 'E';
    q.push({ a,b });

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        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 (A[ny][nx] != c) continue;

            A[ny][nx] = 'E';
            q.push({ ny,nx });
        }
    }
}

void bfs2(int a, int b, char c) {
    queue<pair<int, int>> q;

    B[a][b] = 'E';
    q.push({ a,b });

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        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 (B[ny][nx] != c) continue;

            B[ny][nx] = 'E';
            q.push({ ny,nx });
        }
    }
}

void solution() {
    int n = 0, n2 = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i][j] == 'R' || A[i][j] == 'G' || A[i][j] == 'B') {
                n++;
                bfs(i, j, A[i][j]);
            }
            if (B[i][j] == 'R' || B[i][j] == 'B') {
                n2++;
                bfs2(i, j, B[i][j]);
            }
        }
    }

    cout << n << " " << n2 << endl;
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        string a;
        cin >> a;
        A[i] = a;
        B[i] = a;

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

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글