[알고리즘] 적록색 약

구현 방식

• bfs로 하되 다음 노드로 적합한지 아닌지가, 적록색약인 사람과 아닌 사람에 따라서 다르다.
• 따라서 다음 노드로 적합한지를 함수로 정의하고 함수 포인터를 이용해서 중복을 줄인다.

코드

• 최종 코드는 아래와 같다.

void solution(int N)
{
    int general, colorblind;
    general = countGroups(N, canGo);
    fill(&visited[0][0], &visited[MAXSIZE - 1][MAXSIZE], false);
    colorblind = countGroups(N, canGoColorBlind);
    cout << general << " " << colorblind;
}

int countGroups(int N, bool(*canGoFunc)(pair<int, int> curr, pair<int, int> next, int N))
{
    int result = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            pair<int, int> curr = { i, j };
            if (!visited[curr.first][curr.second])
            {
                bfs(curr, N, canGoFunc);
                result++;
            }
        }
    return result;
}

void bfs(pair<int,int> start, const int N, bool(*canGoFunc)(pair<int, int> curr, pair<int, int> next, int N))
{
    queue<pair<int, int>> q;
    q.push(start);
    visited[start.first][start.second] = true;

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

        for (auto& dir : Directions)
        {
            pair<int, int> next = { curr.first + dir.first , curr.second + dir.second };
            if (canGoFunc(curr, next, N))
            {
                visited[next.first][next.second] = true;
                q.push(next);
            }
        }
    }
}


bool canGo(pair<int, int> curr, pair<int, int> next, int N)
{
    if (next.first < 0 || N <= next.first)
        return false;
    if (next.second < 0 || N <= next.second)
        return false;
    if (graph[next.first][next.second] != graph[curr.first][curr.second])
        return false;

    return !visited[next.first][next.second];
}


bool canGoColorBlind(pair<int, int> curr, pair<int, int> next, int N)
{
    if (next.first < 0 || N <= next.first)
        return false;
    if (next.second < 0 || N <= next.second)
        return false;
    if ((graph[next.first][next.second] != graph[curr.first][curr.second]) && 
        (graph[next.first][next.second] == 'B' || graph[curr.first][curr.second] == 'B'))
        return false;

    return !visited[next.first][next.second];
}