[백준] 10026번 적록색약

문제

 

소스코드

 

#include<iostream>
#include<stack>
#include<vector>
#include<utility>
#include<functional>
 
using Dir = std::pair<int, int>;
using GraphData = std::tuple<int, int, char>;
int g_mapSize{};
 
//범위 탐색용
bool OutofRange(int x, int y) {
    if ((x >= 0 && x < g_mapSize) && (y >= 0 && y < g_mapSize))
        return false;
    return true;
}
 
void DFS(std::vector<std::vector<char>>& v, bool isColorBlindness) {
    /*두 번째 인자값에 따른 함수 객체 */
    std::function<bool(char, char)> compareFunction;
    if (isColorBlindness == false) {
        compareFunction = [](char lhs, char rhs)->bool {
            if (lhs == rhs)
                return true;
            return false;
        };
    }
    else {
        compareFunction = [](char lhs, char rhs)->bool {
            //R과 G를 같은걸로 판단
            if (lhs == 'R' || lhs == 'G') {
                if (rhs == 'R' || rhs == 'G')
                    return true;
            }
            else if (lhs == rhs)
                return true;
            return false;
        };
    }
    //DFS용 스택
    std::stack<GraphData>stack;
    //방문여부
    std::vector<std::vector<bool>>visited(
        g_mapSize + 1, std::vector<bool>(g_mapSize + 1, false));
    //그룹 개수
    int countOfGroup{};
    //우,좌,상,하
    Dir dir[4] = { {0,1},{0,-1},{1,0},{-1,0} };
 
    /*N의 모든 구역을 탐색을 해야 모든 구역을 찾을 수 있다.*/
    for (int x = 0; x < g_mapSize; ++x) {
        for (int y = 0; y < g_mapSize; ++y) {
            //이미 탐색한 노드라면 pass
            if (visited[x][y] == true)continue;
 
            stack.emplace(GraphData{ x,y,v[x][y] });
            visited[x][y] = true;
            while (stack.empty() == false) {
                int x = std::get<0>(stack.top());
                int y = std::get<1>(stack.top());
                char color = std::get<2>(stack.top());
                stack.pop();
 
                //4방향 탐색
                for (int i = 0; i < 4; ++i) {
                    int lx = x + dir[i].first;
                    int ly = y + dir[i].second;
                    
                    //범위 안이라면 탐색  
                    if (OutofRange(lx, ly) == false) {
                        //같은 색상이면서 탐색하지 않은 구역이면 Push
                        if (compareFunction(color,v[lx][ly]) && visited[lx][ly] == false) {
                            visited[lx][ly] = true;
                            stack.emplace(GraphData{ lx,ly,color });
                        }
                    }
                }
            } //while end
            //연관된 모든 구역을 탐색했으니 증가
            ++countOfGroup; 
        } //y for end
    } //x for end
    std::cout << countOfGroup << " ";
}
 
int main() {
    int N;
    std::cin >> N;
    g_mapSize = N;
    std::vector<std::vector<char>>v(N + 1, std::vector<char>(N + 1));
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            char color{};
            std::cin >> color;
            v[i][j] = color;
        }
    }
    //적록색약 O
    DFS(v, false);
    //적록색약 X
    DFS(v, true);
}

 

후기

이 문제를 해결하기 위한 키워드는 DFS이다.

 

기본적 DFS를 베이스로 적록색약 여부에 따라서 비교 객체 함수(compareFunction)를 받아서 두 번 진행하도록 문제를 풀었다.

 

0,0 부터  N까지 DFS를 시작해서 상, 하, 좌, 우 에 있는 같은 색을 찾아서 계속 DFS를 시도하면 문제를 해결할 수 있다.

 

 

 

출처 및 레퍼런스

문제 링크: www.acmicpc.net/problem/10026

 

관련 글

 

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] 깊이 우선 탐색(Depth First Search)

[온라인 코딩/탐색(Search)] - [백준] 1260번 DFS와 BFS