[백준] 10026 적록색약

문제 설명

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

10026번: 적록색약

적록색약이 아닌 사람이 보는 그림의 구역의 수와 적록색약인 사람이 보는 그림의 구역의 수를 구하기

 

문제 풀이법

모든 정점을 방문하는 문제이므로 dfs, bfs 모두 사용할 수 있다

 

그림을 입력 받으면서 R, G, B를 각각 다른 수로 대입하여 배열 arr를 만들어준다

여기서 나는 R을 1, G를 2, B를 3으로 넣어주었다

 

• 적록색약이 아닌 경우
  • R구역의 수를 담는 변수 r, G구역의 수를 담는 변수 g, B구역의 수를 담는 변수 b를 선언한다
  • 해당 좌표에 방문하지 않았고 R이면은 R인 수만을 찾아나서는 dfs/bfs를 돌린 후, r++한다
  • G와 B모두 마찬가지로 각각 dfs/bfs를 돌린다
  • 모든 과정을 끝내면 R구역의 수, G구역의 수, B구역의 수를 다 알게 된다
  • => r + g + b의 값이 적록색약이 아닌 사람이 보는 그림의 구역 수이다
• 적록색약인 경우
  • 적록색약인 경우 R과 G를 같은 구역으로 보기에 R구역과 G구역의 수를 담는 변수 rg를 선언한다
  • 해당 좌표에 방문하지 않았고 R과 G값을 가진, 즉 B가 아닌 수만을 찾아나서는 dfs/bfs를 돌린 후, rg++한다
  • 모든 과정을 끝내면 R구역과 G구역의 수를 알게 된다
  • => 위에서 구한 b + rg의 값이 적록색약인 사람이 보는 그림의 구역 수이다

 

중요한 것은 적록색약이 아닌 경우와 적록색약인 경우에 돌리는 dfs/bfs가 다르다는 것이다

 

소스 코드

bfs

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int n;
int arr[101][101];
int visited[101][101];

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

void bfs(int y, int x, int color)
{
    visited[y][x] = 1;
    
    queue<pair<int, int>> q;
    q.push({y, x});
    
    while (!q.empty())
    {
        int yy = q.front().first;
        int xx = q.front().second;
        
        q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            
            if (ny < 0 || nx < 0 || ny >= n || nx >= n)
                continue;
            if (arr[ny][nx] != color || visited[ny][nx] == 1)
                continue;
            q.push({ny, nx});
            visited[ny][nx] = 1;
        }
    }
}

void bfs_rg(int y, int x)
{
    visited[y][x] = 1;
    
    queue<pair<int, int>> q;
    q.push({y, x});
    
    while (!q.empty())
    {
        int yy = q.front().first;
        int xx = q.front().second;
        
        q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            
            if (ny < 0 || nx < 0 || ny >= n || nx >= n)
                continue;
            if (arr[ny][nx] == 3 || visited[ny][nx] == 1)
                continue;
            q.push({ny, nx});
            visited[ny][nx] = 1;
        }
    }
}

int main()
{
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < n; j++)
        {
            if (str[j] == 'R')
                arr[i][j] = 1;
            else if (str[j] == 'G')
                arr[i][j] = 2;
            else if (str[j] == 'B')
                arr[i][j] = 3;
            visited[i][j] = 0;
        }
    }
    
    int r = 0;
    int g = 0;
    int b = 0;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] == 1 && visited[i][j] == 0)
            {
                bfs(i, j, 1);
                r++;
            }
            else if (arr[i][j] == 2 && visited[i][j] == 0)
            {
                bfs(i, j, 2);
                g++;
            }
            else if (arr[i][j] == 3 && visited[i][j] == 0)
            {
                bfs(i, j, 3);
                b++;
            }
        }
    }
    
    int rg = 0;
    
    for (int i = 0; i < n; i++)
        fill(visited[i], visited[i] + n, 0);
        
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if ((arr[i][j] == 1 || arr[i][j] == 2) && visited[i][j] == 0)
            {
                bfs_rg(i, j);
                rg++;
            }
        }
    }
    
    printf("%d ", r + g + b);
    printf("%d\n", rg + b);
    return 0;
}

 

dfs

#include <iostream>

using namespace std;

int n;
int arr[101][101];
int visited[101][101];

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

void dfs(int y, int x, int color)
{
    if (visited[y][x] == 1)
        return ;
    visited[y][x] = 1;
        
    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 (arr[ny][nx] != color || visited[ny][nx] == 1)
            continue;
        dfs(ny, nx, color);
    }
}

void dfs_rg(int y, int x)
{
    if (visited[y][x] == 1)
        return ;
    visited[y][x] = 1;
        
    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 (arr[ny][nx] == 3 || visited[ny][nx] == 1)
            continue;
        dfs_rg(ny, nx);
    }
}

int main()
{
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < n; j++)
        {
            if (str[j] == 'R')
                arr[i][j] = 1;
            else if (str[j] == 'G')
                arr[i][j] = 2;
            else if (str[j] == 'B')
                arr[i][j] = 3;
            visited[i][j] = 0;
        }
    }
    
    int r = 0;
    int g = 0;
    int b = 0;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] == 1 && visited[i][j] == 0)
            {
                dfs(i, j, 1);
                r++;
            }
            else if (arr[i][j] == 2 && visited[i][j] == 0)
            {
                dfs(i, j, 2);
                g++;
            }
            else if (arr[i][j] == 3 && visited[i][j] == 0)
            {
                dfs(i, j, 3);
                b++;
            }
        }
    }
    
    int rg = 0;
    
    for (int i = 0; i < n; i++)
        fill(visited[i], visited[i] + n, 0);
        
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if ((arr[i][j] == 1 || arr[i][j] == 2) && visited[i][j] == 0)
            {
                dfs_rg(i, j);
                rg++;
            }
        }
    }
    
    printf("%d ", r + g + b);
    printf("%d\n", rg + b);
    return 0;
}