백준 10026 적록색약

DFS(깊이 우선 탐색)을 활용하는 문제이다. 2D 맵을 쓰는것을 보고 이건 BFS인가 DFS인가 했는데 경로를 찾는게 아니라 일단 DFS로 생각했고, 그쪽 접근이 나쁘지 않았다. 이전에 MST 문제를 풀 때, 2D로 된 섬들이 있는 맵에서 MST를 찾는 문제가 있었다. 해당 문제에서는, 지도에 섬이 몇개 있는지 알아야 했고, 맵에 있는 각 섬 픽셀이 어느 섬에 속해있는지 찾아야 했다. 그 과정에서 DFS를 사용해 섬 그루핑을 했는데, 그것과 거의 동일하게 이번 문제 풀이가 진행된다.

 

 문제 풀이의 흐름은 다음과 같다.

1. 어떤 특정한 픽셀에서 시작한다. 
2. 그 픽셀에서 상하좌우 픽셀을 탐색한다.
3. 넘어온 픽셀이 탐색되지 않은 픽셀이고, 넘어오기 전 픽셀 색과 같으면 탐색 배열에 현재 그룹의 인덱스를 적어둔다.
4. 2번 반복
5. 만약, 이미 탐색된 픽셀이거나 넘어오기 전 픽셀 색과 다르면 탐색을 중지한다.

어떤 픽셀에서 DFS 함수를 실행하면, 해당 픽셀에서 같은 색의 그룹을 찾을 수 있다. 해당 그룹은 탐색 배열에 인덱스들로 표시된다.

이제 매 픽셀마다 DFS함수를 실행하면 된다. 특정 그룹에서 처음으로 실행된 픽셀 탐색일때만 전체 DFS 탐색이 되고, 그 때 탐색 배열에 표시를 하게 되므로, 이미 그루핑이 된 픽셀은 DFS탐색이 되지 않는다. 탐색이 완료되어 새 그룹이 된 경우 true를 리턴해 그룹 인덱스를 1 더해준다.

 

이제 정상시야와 적록색약을 구분하면 되는데, 그냥 똑같은 로직에 똑같은 배열을 하나 더 만드는 것으로 해결했다. N*N 맵으로 탐색을 하게 되는데, N이 100으로 크지 않기때문에 똑같은 맵을 하나 더 만들어도 메모리가 초과되지 않을 것이다. 정상시야의 경우, 탐색할 때 계속 같은 색일 경우 탐색이 진행되었다. 적록색약일 경우, 해당 조건을 살짝 바꿔 R일때 R, G인 경우, G 일때 R, G인 경우, B 일때 B일 경우 탐색을 계속하도록 if 문만 바꿨다. 템플릿으로 만들어서 깔끔하게 할 수도 있을 것 같다.

 

코드는 다음과 같다.

#include <iostream>
#include <string.h>

char MAP[100][100];
int CW[100][100];
int NV[100][100];
int NVGroup = 0;
int CWGroup = 0;
int N;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int GroupNV(int y, int x, char color)
{
    if (y<0 || x <0 || x > N-1 || y >N-1)
        return 0;
    if (NV[y][x] == -1)
    {
        if (MAP[y][x] == color)
        {
            NV[y][x] = NVGroup;
            for (int i = 0; i < 4; i++)
                GroupNV(y+dy[i], x+dx[i], color);
            return 1;
        }
        return 0;
    }
    return 0;
}

void NormalVision()
{
    for (int y = 0 ; y < N; y++)
    {
        for (int x = 0; x < N; x++)
        {
            int groupped = GroupNV(y, x, MAP[y][x]);
            if (groupped)
                NVGroup++;
        }
    }
}

int GroupCW(int y, int x, char color)
{
    if (y<0 || x <0 || x > N-1 || y >N-1)
        return 0;
    if (CW[y][x] == -1)
    {
        if (MAP[y][x] == color || (MAP[y][x] == 'R' && color == 'G') || (MAP[y][x] == 'G' && color == 'R'))
        {
            CW[y][x] = CWGroup;
            for (int i = 0; i < 4; i++)
                GroupCW(y+dy[i], x+dx[i], color);
            return 1;
        }
        return 0;
    }
    return 0;
}

void ColorWeakness()
{
    for (int y = 0 ; y < N; y++)
    {
        for (int x = 0; x < N; x++)
        {
            int groupped = GroupCW(y, x, MAP[y][x]);
            if (groupped)
                CWGroup++;
        }
    }
}

int main()
{
    std::cin >> N;
    memset(CW, -1, sizeof(CW));
    memset(NV, -1, sizeof(NV));

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N ; j++)
        {
            std::cin >> MAP[i][j];
        }
    }

    NormalVision();
    ColorWeakness();

    std::cout << NVGroup << " " << CWGroup ;
}

 

한줄만 다른 함수가 두개씩 있으니 좀 보기 그렇긴 하다. 이 문제는 거의 2D 맵 DFS의 스탠다드라고 할 수 있는것 같다.

페북이나 인스타를 들어가지 말아야겠다... 왜 거기는 다 잘난사람들이 있는거지... ㅏ하ㅏ하...

 

오늘도 평온한 하루가 되길. 슨민.