백준 10026 : 적록색약

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

 

---

문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

---

생각

1. 일단 bfs든 dfs든 풀면 가능할거 같다
2. 타입이 2개니까 2번 작성해야 하나?
3. R, G를 같은 걸로 놓고 풀면 되겠다

---

코드

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


using namespace std;

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

int BFS(vector<string>& pitchers, bool color)
{
    int size = pitchers.size();
    vector<vector<bool>> visited(size, vector<bool>(size, false)); 

    queue<pair<int, int>> q;

    int count = 0;

    for(int ix = 0; ix < size; ++ix)
    {
        for(int jx = 0; jx < size; ++jx)
        {
            if(!visited[ix][jx])
            {
                ++count;
                visited[ix][jx] = true;
                q.push({ix, jx});
                while(!q.empty())
                {
                    auto[cur_x, cur_y] = q.front();
                    q.pop();

                    for(int k = 0; k < 4; ++k)
                    {
                        int nex_x = cur_x + dx[k];
                        int nex_y = cur_y + dy[k];

                        if(nex_x >= 0 && nex_x < size && nex_y >= 0 && nex_y < size)
                        {
                            if(!visited[nex_x][nex_y])
                            {
                                if(color)
                                {
                                    if(pitchers[cur_x][cur_y] == pitchers[nex_x][nex_y])
                                    {
                                        q.push({nex_x, nex_y});
                                        visited[nex_x][nex_y] = true;
                                    }
                                }
                                else
                                {
                                    if(((pitchers[cur_x][cur_y] == 'R' || pitchers[cur_x][cur_y] == 'G') && (pitchers[nex_x][nex_y] == 'R' || pitchers[nex_x][nex_y] == 'G')) || pitchers[cur_x][cur_y] == pitchers[nex_x][nex_y])
                                    {
                                        q.push({nex_x, nex_y});
                                        visited[nex_x][nex_y] = true;
                                    }
                                }
                            }
                            
                        }
                    }
                }
            }
        }
    }
    return count;
}

int main()
{
    int n;
    cin >> n;

    vector<string> pitchers(n);
    for(int ix = 0; ix < n; ++ix)
    {
        cin >> pitchers[ix];
    }

    
    cout << BFS(pitchers, true) << " " << BFS(pitchers, false);
    
}

---

틀린 이유

•  

if(!visited[nex_x][nex_y])
                            {
                                if(color)
                                {
                                    if(pitchers[cur_x][cur_y] == pitchers[nex_x][nex_y])
                                    {
                                        q.push({nex_x, nex_y});
                                        visited[nex_x][nex_y] = true;
                                    }
                                }
                                else
                                {
                                    if((pitchers[cur_x][cur_y] == 'R' || pitchers[cur_x][cur_y] == 'G') && (pitchers[nex_x][nex_y] == 'R' || pitchers[nex_x][nex_y] == 'G') || pitchers[cur_x][cur_y] == pitchers[nex_x][nex_y])
                                    {
                                        q.push({nex_x, nex_y});
                                        visited[nex_x][nex_y] = true;
                                    }
                                }
                            }

색약 부분의 조건문을 잘못 작성했던 적이 있었음 -> 한번더묶어 줬어야 했었는데 안했음 

---

수정 코드

if(nex_x >= 0 && nex_x < size && nex_y >= 0 && nex_y < size)
                        {
                            if(!visited[nex_x][nex_y])
                            {
                                if(color)
                                {
                                    if(pitchers[cur_x][cur_y] == pitchers[nex_x][nex_y])
                                    {
                                        q.push({nex_x, nex_y});
                                        visited[nex_x][nex_y] = true;
                                    }
                                }
                                else
                                {
                                    if(((pitchers[cur_x][cur_y] == 'R' || pitchers[cur_x][cur_y] == 'G') && (pitchers[nex_x][nex_y] == 'R' || pitchers[nex_x][nex_y] == 'G')) || pitchers[cur_x][cur_y] == pitchers[nex_x][nex_y])
                                    {
                                        q.push({nex_x, nex_y});
                                        visited[nex_x][nex_y] = true;
                                    }
                                }
                            }
                            
                        }

---

결과

• 메모리 :  2028KB
• 시간 :  0ms