[BFS/DFS] C11 백준 10026 적록색약 풀이

문제

• 10026

풀이 과정

• 적록색약에 따라 그림 구역을 세는 문제 -> bfs다
  • 적록색약일 때는 R,G를 같이 카운팅
  • 아닐 때는 R,G,B 따로 카운팅
• 이것도 쉬운 문제긴 한데 코드가 늘어진다... 하나의 bfs에서 적록색약인지 아닌지 flag주고 돌아도 될 것 같은데 일단 무작정 구현했다 ㅋㅋㅋㅋㅋㅋㅎㅎ..
• BFS, 자료구조는 큐

#include <stdio.h>

#define MAX 101

typedef struct Que {
    int x;
    int y;
} Q;

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

int n;
char map[MAX][MAX];
int visit[MAX][MAX];

Q que[MAX*MAX];
int front;
int rear;

void enqueue(int x, int y) {
    que[rear].x = x;
    que[rear].y = y;
    rear++;
}

Q dequeue() {
    return que[front++];
}

void bfsgeneral(char color) {
    while (front < rear) {
        Q cur = dequeue();
        
        for (int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
                map[nx][ny] == color && visit[nx][ny] == 0) {
                visit[nx][ny] = 1;
                enqueue(nx, ny);
            } 
        }
    }
}

void bfscolorblind() {
    while (front < rear) {
        Q cur = dequeue();
        
        for (int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
               (map[nx][ny] == 'R' || map[nx][ny] == 'G') && visit[nx][ny] == 0) {
                visit[nx][ny] = 1;
                enqueue(nx, ny);
            } 
        }
    }
}

int main() {
    scanf("%d", &n);
    
    for (int i=0; i<n; i++) {
        scanf("%s", map[i]);
    }
        
    int result1 = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (visit[i][j] == 0) {
                result1++;
                visit[i][j] = 1;
                enqueue(i, j);
                bfsgeneral(map[i][j]);
            }
        }
    }
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            visit[i][j] = 0;
        }
    }
    front = 0;
    rear = 0;
    
    int result2 = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (visit[i][j] == 0) {
                result2++;
                visit[i][j] = 1;
                enqueue(i, j);
                
                if (map[i][j] == 'R' || map[i][j] == 'G') {
                    bfscolorblind();
                } else {
                    bfsgeneral(map[i][j]);
                }
            }
        }
    }
    
    printf("%d %d", result1, result2);
    return 0;
}