문제

문제 링크

구역을 r,g,b로 나누는데
일반인 눈에는 r,g,b 3개로 보여서 3개로 나누고
적록색맹 눈에는 r+g,b 2개로 보여서 r,g를 같은색으로 취급해서 나눈다.

문제를 해석하면 그룹을 나눠서 몇개의 그룹이 되는지를 체크하는 문제다.
그래서 각 좌표마다 중복방문하지 않고 bfs로 이동하면된다.

여기서 그룹간에 거리를 구한다던지 다른 연산이 있으면 union-find로 같은 그룹인지 체크도 할 수 있을듯 하다.

문자열 입력 문제

코드를 다 작성해서 테스트 해보는데 계속 입력이 제대로 되지 않았다.
문제는 내가 char 배열을 동적할당 해주지 않았다.

먼저 처음 작성한 코드다.

// 동적할당 x
// for 문 반복
char line[100];
scanf("%s",line);
group.push_back(line);

문자열을 입력받고 벡터에 넣어줬는데
나중에 확인해보니
마지막 받은 문자열이 중복해서 들어가있었다.

왜 그럴까?
원인은 같은 주소를 가진 line 문자열을 덮어써주고 벡터에 넣어
모두 같은 주소를 갖는 문자열이었다.

그래서 매번 새로운 문자열임을 나타내기위해 동적할당해주었다.

// 동적할당 o
char *line = new line[100];
scanf("%s",line);
group.push_back(line);

code

/**
 * 백준 10026
 * bfs
 * r,g,b에 지역 구분하기
 * r+g,b 지역 구분하기
*/
#include <bits/stdc++.h>
using namespace std;

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

int cntGroup(vector<char*> group){
    int groupCnt=0;
    bool visited[100][100]={false};
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!visited[i][j]){
                groupCnt++;
                visited[i][j]=true;
                char color=group[i][j];

                queue<pair<int,int>> que;
                que.push(make_pair(i,j));

                while(!que.empty()){
                    pair<int,int> now = que.front();
                    que.pop();

                    for(int idx=0;idx<4;idx++){
                        int my=now.first+dy[idx];
                        int mx=now.second+dx[idx];

                        if(my<0 || my>=n || mx<0 || mx>=n){
                            continue;
                        }
                        char groupColor=group[my][mx];
                        if(!visited[my][mx] && color==groupColor){
                            visited[my][mx]=true;
                            que.push(make_pair(my,mx));
                        }
                    }
                }
            }
        }
    }
    return groupCnt;
}

int cntBlindGroup(vector<char*> group){
    int groupCnt=0;
    bool visited[100][100]={false};
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!visited[i][j]){
                groupCnt++;
                visited[i][j]=true;
                char color=group[i][j];

                queue<pair<int,int>> que;
                que.push(make_pair(i,j));

                while(!que.empty()){
                    pair<int,int> now = que.front();
                    que.pop();

                    for(int idx=0;idx<4;idx++){
                        int my=now.first+dy[idx];
                        int mx=now.second+dx[idx];

                        if(my<0 || my>=n || mx<0 || mx>=n){
                            continue;
                        }
                        char groupColor=group[my][mx];
                        if(!visited[my][mx] && (color==groupColor 
                            || (color=='R' && groupColor=='G')
                            || (color=='G' && groupColor=='R'))){
                            visited[my][mx]=true;
                            que.push(make_pair(my,mx));
                        }
                    }
                }
            }
        }
    }
    return groupCnt;
}

int main(void){
    cin>>n;
    vector<char*> group;
    for(int i=0;i<n;i++){
        char *line = new char[100];
        scanf("%s",line);
        group.push_back(line);
    }
    cout<<cntGroup(group)<<" "<<cntBlindGroup(group)<<endl;
}