[BOJ알고리즘, C++]#10026_적록색약, 그래프 탐색, DFS, 재귀 호출, 영역 찾기

 

#1. 문제

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

10026번: 적록색약

 

---

 

#2. 풀이

 

1. 그래프 탐색, DFS

https://webddevys.tistory.com/291#%232.%20%ED%83%90%EC%83%89-1

[자료구조]#6_그래프

 

DFS(깊이 우선 탐색)은 그래프의 모든 정점을 탐색하는 방법 중 하나로, 출발 정점으로부터 더 이상 확장할 수 없는 단말 노드까지 우선적으로 탐색하여, 최종적으로 모든 정점을 탐색합니다. 일반적으로, DFS는 재귀 호출 혹은 스택 자료구조를 활용하여 구현 가능합니다.

 

2. 적록색약이라면, 'R'을 모두 'G'로 바꿔버리자!

 

1. 먼저, 적록색약이 없는 경우의 DFS를 수행해 줍니다.
2. 다음으로, 모든 구역을 한 번 순회하며, 'R' 값을 갖는 구역이라면 'G' 값으로 변경해 줍니다.
3. 마지막으로, 적록색약이 있는 경우의 DFS를 한번 더 수행해 줍니다.

 

---

 

#3. 코드

 

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

using namespace std;

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

void dfs(vector<string> &grid, vector<vector<bool>> &visited, int x, int y, char color)
{
    visited[x][y] = true;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && ny >= 0 && nx < grid.size() && ny < grid.size())
            if (!visited[nx][ny] && grid[nx][ny] == color)
                dfs(grid, visited, nx, ny, color);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<string> grid(N);
    for (int i = 0; i < N; i++)
        cin >> grid[i];

    vector<vector<bool>> visited(N, vector<bool>(N, false));
    int normal = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (!visited[i][j])
            {
                dfs(grid, visited, i, j, grid[i][j]);
                normal++;
            }

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (grid[i][j] == 'G')
                grid[i][j] = 'R';

    visited = vector<vector<bool>>(N, vector<bool>(N, false));
    int colorBlind = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (!visited[i][j])
            {
                dfs(grid, visited, i, j, grid[i][j]);
                colorBlind++;
            }

    cout << normal << " " << colorBlind << "\n";

    return 0;
}

 

---