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

1. 문제

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

10026번: 적록색약

2. 접근법

1. 굳이 3차원배열로 안풀어도 될거같은데 저번주에 3차원배열로 푸는거에 꽂혀서 3차원 배열로 풀어봤다..
2. 적록색약인사람과 아닌사람의 방문체크배열을 따로 만들면 됐지만 나는 그냥 3차원 배열로 했다.
3. 이것도 구역의 갯수를 구하는 것이기때문에 모든 정점을 다 방문해야 될것이라고 판단.
4. 영역의 각 넓이는 구하지 않아도 되므로 전역변수로 area_cnt를 두고 영역의 갯수를 카운팅한다.

3. 문제풀이

1. 일단 char배열을 갖고 문제풀기가 싫어서 int map[][] 배열을 만들었다.
2. 삼중 for문을 돌면서 bfs를 돌린다. 일단 적록색약이 아닌사람 먼저 -> 적록색약인사람 을 구함!!
3. 큐에는 x,y값과 color값을 넣는다 (이유는 같은색인지 아닌지를 판단하기 위해서)
4. 다음 탐색할 정점의 색과 큐에서 pop한 정점의 색이 같다면 다음 탐색을 계속 진행. 아니라면 탈락
5. 단, 적록색약인 사람의 경우, R과 G를 같은 색으로 보기 때문에 44번째줄 조건을 넣어주면된다.

4. 전체코드

#include <iostream>
#include <string>
#include <queue>
using namespace std;
 
struct Pos {
    int x;
    int y;
    int color;
};
 
int n;//map의 크기
char map[101][101];
int map2[101][101];
int dp[2][101][101];//적록색약이 아닌사람 : 0, 적록색약인사람 1
 
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
 
int area_cnt;
queue<Pos> q;
 
void bfs(int x, int y, int color, int k) {
    q.push({ x, y, color });
    dp[k][x][y] = area_cnt;
 
    while (!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        color = q.front().color;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nColor = map2[nx][ny];
 
            if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                if (k == 0 && dp[0][nx][ny] == 0 && nColor == color) {
                    q.push({ nx, ny, nColor });
                    dp[0][nx][ny] = area_cnt;
                }
                else if (k == 1 && dp[1][nx][ny] == 0) {
                    if ((color == nColor) || (color == 0 && nColor == 1) || (color == 1 && nColor == 0)) {
                        q.push({ nx, ny, nColor });
                        dp[1][nx][ny] = area_cnt;
                    }
                }
            }
        }
    }
}
 
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 'R') {
                map2[i][j] = 0;
            }
            else if (map[i][j] == 'G') {
                map2[i][j] = 1;
            }
            else if (map[i][j] == 'B') {
                map2[i][j] = 2;
            }
        }
    }
 
    for (int k = 0; k < 2; k++) {
        area_cnt = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[k][i][j] == 0) {
                    bfs(i, j, map2[i][j], k);
                    area_cnt++;
                }
            }
        }
        cout << area_cnt - 1 << " "; //마지막에 나올때 ++해서 나오기때문에 -1 해준다.
                        //아오...dp마지막줄에서 최대값을 구하면 될줄 알았는데,,생각해보니까 중간줄이 더 클수도있음..
    }
    return 0;
}