백준 10026 적록색약(c++)

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

10026번: 적록색약

백준 골드5 난이도이고, 비교적 간단한 DFS 였습니다.

적록색약인 사람(빨강, 초록 구분 x)이랑, 적록색약이 아닌 사람(빨강, 초록 구분 o)의 DFS 함수를 각각 따로 만들어주었습니다.

적록색약인 사람의 경우에는 기준점이 빨강이면, DFS함수를 돌렸을 때 상하좌우의 배열값이 빨강이랑 초록이면 DFS함수를 재귀적으로 돌려주는 방향으로 알고리즘을 설계하였습니다.

그렇지 않은 경우(파랑)일 때는, 그냥 배열값이 파랑이면 되기 때문에 비교적 쉽게 만들 수 있었습니다.

 

적록색약이 아닌 사람의 경우는 기존 DFS 풀이 방식대로, 기준점에서 상하좌우 값이 같다면, DFS함수를 호출하는 방향으로 설계해 주었습니다.

 

이 문제에서 주의해야 할 점은 함수를 따로 만들어주었고, visited(방문 여부)를 다시 초기화해주어야 한다는 점입니다.(적록색약인 사람인 경우에는 새롭게 DFS함수를 호출하기 때문입니다)

 

 

 

<코드>

#include <iostream>
#include <cstring>

using namespace std;

bool visited[101][101];
char board[101][101];
int n;
int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int cnt1 = 0;
int cnt2 = 0;
void dfs_colorbilndness(int x, int y)
{
    visited[x][y] = true;
    for(int i=0;i<4;i++)
    {
        int row = x + mov[i][0];
        int col = y + mov[i][1];

        if(board[x][y]=='R' || board[x][y]== 'G')
        {
            if(row>=0 && col>=0 && row < n && col < n && !visited[row][col])
            {
                if(board[row][col]=='R' || board[row][col]=='G')
                {
                    visited[row][col] = true;
                    dfs_colorbilndness(row,col);
                }
            }
        }
        else
        {
            if(row>=0 && col>=0 && row < n && col < n && !visited[row][col])
            {
                if(board[row][col]==board[x][y])
                {
                    visited[row][col] = true;
                    dfs_colorbilndness(row,col);
                }
            }
        }
    }
}

void dfs(int x,int y)
{
    visited[x][y] = true;
    for(int i=0;i<4;i++)
    {
        int r = x + mov[i][0];
        int c = y + mov[i][1];

        if(r>=0 && c>=0 && r<n && c<n && !visited[r][c] && board[x][y]==board[r][c])
        {
            dfs(r,c);
        }
    }
}

int main()
{

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

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(!visited[i][j])
            {
                dfs(i,j);
                cnt1++;
            }
        }
    }
    memset(visited,false,sizeof(visited));

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(!visited[i][j])
            {
                dfs_colorbilndness(i,j);
                cnt2++;
            }
        }
    }

    cout<<cnt1<<' '<<cnt2<<'\n';

}

 

다른 사람의 풀이를 보니, 우선적으로 적록색약이 아닌 사람의 경우의 수를 구한 다음, 빨간색과 초록색인 경우에 하나의 색으로 교체해서 DFS함수를 돌려줬습니다. 저는 개인적으로 색을 바꿔주고, 하나의 함수를 호출하는 것이 좋다고 생각합니다.