10026번 적록색약 | DFS | 백준 10026 C++ 코드

 

 

이번 포스팅은 백준 10026번 적록색약입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/10026

10026번: 적록색약

 

 

 

기본 알고리즘

DFS 깊이 우선 탐색

 

 

 

전체 코드

 

//백준10026 적록색약                                                            
 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
int N;
const int MAX = 101;
char map[MAX][MAX];
bool visited[MAX][MAX] = { 0, };
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };
 
void DFS_R(int y, int x) {
    visited[y][x] = true;
 
    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 (map[ny][nx] == 'R' && visited[ny][nx] == 0) {
            visited[ny][nx] = true;
            DFS_R(ny, nx);
        }
    }
}
 
void DFS_G(int y, int x) {
    visited[y][x] = true;
 
    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 (map[ny][nx] == 'G' && visited[ny][nx] == 0) {
            visited[ny][nx] = true;
            DFS_G(ny, nx);
        }
    }
}
 
void DFS_B(int y, int x) {
    visited[y][x] = true;
 
    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 (map[ny][nx] == 'B' && visited[ny][nx] == 0) {
            visited[ny][nx] = true;
            DFS_B(ny, nx);
        }
    }
}
 
void resetVisit() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visited[i][j] = 0;
        }
    }
}
 
int main() {
    
    /*입력 받기*/
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%1s", &map[i][j]);
        }
    }
 
    int cntR = 0; //R구역 개수
    int cntG = 0; //G구역 개수
    int cntB = 0; //B구역 개수
    int notColorBlind = 0; //적록색약 아닌 사람이 보는 구역의 수
    
    /*R,G,B 각각 DFS*/
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 'R' && visited[i][j] == 0) {
                DFS_R(i, j);
                cntR++;
            }
            if (map[i][j] == 'G' && visited[i][j] == 0) {
                DFS_G(i, j);
                cntG++;
            }
            if (map[i][j] == 'B' && visited[i][j] == 0) {
                DFS_B(i, j);
                cntB++;
            }
        }
    }
    notColorBlind = cntR + cntG + cntB;
 
    /*visited 초기화*/
    resetVisit();
 
    cntR = 0; //R구역 개수 초기화
    int colorBlind = 0; //적록색약인 사람이 보는 구역의 수
 
    /*map에서 G를 전부 R로 변환*/
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 'G') {
                map[i][j] = 'R';
            }
        }
    }
    /*R로 변환된 G를 합한 R 구역 DFS*/
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 'R' && visited[i][j] == 0) {
                DFS_R(i, j);
                cntR++;
            }
        }
    }
    colorBlind = cntR + cntB;
 
 
    cout << notColorBlind << " " << colorBlind;
 
}