백준 10026 적록색약 c++ (bfs)

문제 출처 : https://www.acmicpc.net/problem/10026

10026번: 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

bfs로 영역들을 확인해가며 영역의 개수를 찾는 문제이다.

적록색약인 사람은 R과G는 같은 색, 즉 R과 G과 같이 있으면 같은 영역으로 보고,

일반 사람은 R, G, B 세 개의 색으로 구분하여 색상 별로 모두 다른 영역으로 본다.

 

풀이는 순서는 아래와 같다.

1.주어진 문자들로 그래프를 만든다.

2.일반 사람, 적록색약인 사람 두 가지의 경우를 구해야 하기 때문에 원본 그래프는 냅두고 복사한다.

3.복사한 그래프의 시작지점 0,0부터 탐색하여 아직 방문하지 않은 칸을 시작으로 bfs를 실행한다.

4.한 번 bfs를 돌면 시작 지점과 인접한 칸의 같은 색상은 방문했다는 표시로 'O'로 바꿔준다.

5.복사한 그래프를 모두 'O'으로 만들면 영역의 개수를 출력한다.

 

 

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int n;
void bfs(int row, int col, vector<vector<char>> &graph, int seq) {
    char color = graph[row][col];
    queue<pair<int, int>> q;
    q.push({ row, col });
    graph[row][col] = 'O';
    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int next_r = r + dir[i][0];
            int next_c = c + dir[i][1];
            if (seq == 0 || color=='B') {//적록색약이 아니거나 색이 blue일 때
                if (next_r >= 0 && next_r < n && next_c >= 0 && next_c < n&&graph[next_r][next_c] == color) {
                    q.push({ next_r,next_c });
                    graph[next_r][next_c] = 'O';
                }
            }
            else {//적록색약이면서 색이 red나green일 때
                if (next_r >= 0 && next_r < n && next_c >= 0 && next_c < n&&(graph[next_r][next_c] == 'R'|| graph[next_r][next_c] == 'G')) {
                    q.push({ next_r,next_c });
                    graph[next_r][next_c] = 'O';
                }
            }

        }
    }

}

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

    cin >> n;
    vector<vector<char>> graph(n, vector<char>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    int count;
    for (int seq = 0; seq < 2; seq++) { //seq==1 일반 사람 seq==2 적록색약
        vector<vector<char>> graph_copy(graph);
        count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph_copy[i][j] != 'O') {//방문한 칸은 O으로 변경
                    bfs(i, j, graph_copy, seq);
                    count++;
                }
            }            
        }
        cout << count << ' ';
    }

    return 0;
}