[C++][백준 10026] 적록색약

[문제]

10026번: 적록색약 (acmicpc.net)

10026번: 적록색약

[문제 풀이]

BFS를 돌리는데 적녹색약인 사람은 R와 G을 일치시켜서 본다. 그렇기에 BFS를 2번 돌리는데 한번은 지금 위치가 R나 G이고 다음 사람도 R나 G이면 똑같이 방문이 가능하게 하고 한번은 아니게 접근을 하였다.

틀린 풀이는 아니었지만 결과적으로 코드가 너무 길어져버리는 문제가 발생했다. BFS함수에 char를 인자로 넣어서 어떻게든 할려고도 했으나 생각보다 구현이 쉽지 않았고 이에 다른 사람들의 답을 보고 수정을 하였다.

두번째로는 접근을 할때 아예 board 배열에 있는 R나 G를 하나로 모두 통일을 시키고 BFS를 돌렸다. 이렇게 만드니 코드적으로 기존보다 훨씬 간편해졌다는 장점이 있었다.

[회고]

코드가 너무 길어서 노가다성이 짙다고 생각했지만 함수의 재사용을 얼마든 할 수 있는 부분이었다. 조금 더 고민을 해보자.

[코드]

<처음 코드>

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

using namespace std;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int visited[110][110];
char board[110][110];
int n;

void bfs(int x, int y){
    //1. R하고 G 구분 못함.
    //2. 모두 구분함.

    queue<pair<int, int> > q;
    q.push(make_pair(x,y));

    while(q.size() > 0 ){
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(nextX >= 0 and nextX < n and nextY >= 0 and nextY < n){
                if(visited[nextX][nextY] == 0){
                    if(board[nextX][nextY] == board[curX][curY]){
                        visited[nextX][nextY] = 1;
                        q.push(make_pair(nextX,nextY));
                    }
                }
            }
        }
    }
    return;
}

void bfs2(int x, int y){
    //1. R하고 G 구분 못함.

    queue<pair<int, int> > q;
    q.push(make_pair(x,y));

    while(q.size() > 0 ){
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(nextX >= 0 and nextX < n and nextY >= 0 and nextY < n){
                if(visited[nextX][nextY] == 0){
                    if(board[curX][curY] == 'R' || board[curX][curY] == 'G'){
                        if(board[nextX][nextY] == 'R' || board[nextX][nextY] == 'G'){
                            visited[nextX][nextY] = 1;
                            q.push(make_pair(nextX,nextY));
                        }
                    }
                    else if(board[curX][curY] == 'B' and board[nextX][nextY] == board[curX][curY]){
                        visited[nextX][nextY] = 1;
                        q.push(make_pair(nextX,nextY));
                    }
                }
            }
        }
    }
    return;
}


int main(){
    cin>>n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin>>board[i][j];
        }
    }

    int answer = 0;
    int secondAnswer = 0;

    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(visited[i][j] == 0){
                bfs(i,j);
                answer++;
            }
        }
    }

    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            visited[i][j] = 0;
        }
    }

    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(visited[i][j] == 0){
                bfs2(i,j);
                secondAnswer++;
            }
        }
    }

    cout<<answer<<" "<<secondAnswer<<endl;



    return 0;
}

<마지막 코드>

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

using namespace std;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int visited[110][110];
char board[110][110];
int n;

void bfs(int x, int y){
    //1. R하고 G 구분 못함.
    //2. 모두 구분함.

    queue<pair<int, int> > q;
    q.push(make_pair(x,y));

    while(q.size() > 0 ){
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(nextX >= 0 and nextX < n and nextY >= 0 and nextY < n){
                if(visited[nextX][nextY] == 0){
                    if(board[nextX][nextY] == board[curX][curY]){
                        visited[nextX][nextY] = 1;
                        q.push(make_pair(nextX,nextY));
                    }
                }
            }
        }
    }
    return;
}

int operateBFS(){
    int answer = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(visited[i][j] == 0){
                bfs(i,j);
                answer++;
            }
        }
    }
    return answer;
}

int main(){
    cin>>n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin>>board[i][j];
        }
    }

    int answer = 0;
    int secondAnswer = 0;

    answer = operateBFS();

    //visited 초기화 && boad에서 적녹색약이 구별을 못하니 Red를 모두 Green으로 바꾸자.ㄴ
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            visited[i][j] = 0;
            if(board[i][j] == 'R'){
                board[i][j] = 'G';
            }
        }
    }

    //다시 한번 bfs돌리기.
    secondAnswer = operateBFS();
    
    cout<<answer<<" "<<secondAnswer<<endl;


    return 0;
}