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

[문제보기]

 

[해결과정]

 1. input

  -> n, arr 입력받기

 

 2. 정상인 사람이 볼 때,

  -> arr을 순회하며, 방문체크가 안되있는 좌표를 queue에 넣고 bfs수행,

  -> 진입할 때, 방문체크 하고 gNum++ (그룹수)

  -> bfs(0) 플래그 0으로 진입

 

 3. bfs(0)

  -> bfs수행 하는데, flag가 0인 부분으로 진입

 

 4. 적록색약인 사람이 볼 때,

  -> 먼저 check 배열 초기화, gNum = 0으로 변경

  -> 맵을 순회하며 R을 G로 바꾸거나 혹은 G를 R로 다 바꿔버림.

 

 5. 적록색약인 사람이 볼 때 기능 실행

  -> arr을 순회하며, 방문체크가 안되있는 좌표를 queue에 넣고 bfs수행,

  -> 진입할 때, 방문체크 하고 gNum++ (그룹수)

  -> bfs(1) 플래그 1로 진입

 

 6. c가 R혹은 G이면, 다음 방문 할 곳이 R혹은 G 둘 중 하나이면 진입.

 

 7. output

 

 

[소스코드]

/*
    BOJ 10026 - 적록색약 
    Created by haejun on 2020/03/18
*/
#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;
const int MAX = 102;
 
int n;
char arr[MAX][MAX];
bool check[MAX][MAX];
 
//그룹
int gNum;
 
struct coor {
    int y;
    int x;
    int rgb;
};
queue<coor> q;
 
// inside check
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < n;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void bfs(int flag) {
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        char c = q.front().rgb;
        q.pop();
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (inside(ny, nx) && check[ny][nx] == 0) {
                if (flag == 1) {
                    if ((c == 'R' || c == 'G') && (arr[ny][nx] == 'R' || arr[ny][nx] == 'G')) {
                        check[ny][nx] = 1;
                        q.push({ ny,nx,'R' });
                    }
                    else {
                        if (c == arr[ny][nx]) {
                            check[ny][nx] = 1;
                            q.push({ ny,nx,c });
                        }
                    }
                }
                else {
                    if (c == arr[ny][nx]) {
                        check[ny][nx] = 1;
                        q.push({ ny,nx,c });
                    }
                }
                
            }
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
 
    //정상인 사람이 볼 때,
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == 0) {
                check[i][j] = 1;
                q.push({ i,j,arr[i][j] });
                bfs(0);
                gNum++;
            }
        }
    }
    cout << gNum << "\n";
 
    //적록색약인 사람이 볼 때,
    memset(check, 0, sizeof(check));
    gNum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 'G') arr[i][j] = 'R';
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == 0) {
                check[i][j] = 1;
                q.push({ i,j,arr[i][j] });
                bfs(1);
                gNum++;
            }
        }
    }
    cout << gNum << "\n";
    
    
 
 
    return 0;
}

 

[해결 과정 중 실수한 부분 / 잡담]

 없음

 

[관련 문제 혹은 비슷한 문제]

 없음