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

유형

2차원 배열의 인접한 부분을 bool형 배열로 체크해가며 탐색하는 문제이다.

비슷한 문제를 풀어본 적이 없다면,

해결의 실마리조차 모르겠다면 아래 글을 참고하자.

 

2021.09.26 - [PS/백준] - 백준 4963번 (C++) 섬의 개수

백준 4963번 (C++) 섬의 개수

 

구현 아이디어

bfs로 탐색하면서, 탐색한 곳은 bool 배열로 체크해주면 

섬처럼 묶인 부분들의 개수를 셀 수 있다.

적록색약인 경우와 아닌 경우 각각의 탐색 조건이 다를 것이다.

 

이를테면 색약인 경우 초록색과 빨간색을 구분하여 탐색하면 안된다.

그러므로 색약의 경우 호출하는 함수(bfs2)에서는

1. 현재의 색 (arr[x][y])와 탐색할 색(arr[nx][ny])가 같으면
2. 현재의 색이 red, 다음 탐색할 색이 green이면
3. 다음의 색이 red, 현재의 색이 green이면

세 가지 조건 중 하나라면 이어졌다(인접해있다, 연결되어있다)고 볼 수 있다.

 

 

나는 너비 우선 탐색을 사용했으나, 깊이 우선 탐색을 사용하여도 해결할 수 있는 문제이다.

깊이 우선 탐색으로 구현하다가 막혀서 이 글을 보게되었다면, 먼저 자신이 선택한 방법으로 끝까지 구현해보길 감히 추천한다...

 

 

DFS로 구현하기

 

2021.11.27 - [PS/백준] - 백준 2583 (C++) 영역 구하기

백준 2583 (C++) 영역 구하기

 

위 글을 참조하면 dfs로 비슷한 문제를 해결하는 코드를 볼 수 있다.

 

 

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
using ll = long long;

int n, m, cnt1 = 0, cnt2 = 0;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
char arr[102][102];
bool visited[102][102];
string s;

void bfs(int i, int j) {
    queue<pair<int, int> > q;
    q.push({i, j});
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        // visited[x][y] = true;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 | ny >= m) {
                continue;
            }
            if (!visited[nx][ny] && arr[x][y] == arr[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    return;
}

void bfs2(int i, int j) { // 적록색맹의 경우
    queue<pair<int, int> > q;
    q.push({i, j});
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        //visited[x][y] = true;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 | ny >= m || visited[nx][ny]) {
                continue;
            }
            if (arr[x][y] == arr[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
            else if (arr[x][y] == 'R' && arr[nx][ny] == 'G') {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
            else if (arr[x][y] == 'G' && arr[nx][ny] == 'R') {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    return;
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            arr[i][j] = s[j];
            visited[i][j] = false;
        }
    }
    m = s.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j]) {
                bfs(i, j);
                cnt1++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            visited[i][j] = false;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j]) {
                bfs2(i, j);
                cnt2++;
            }
        }
    }
    cout << cnt1 << " " << cnt2;
    return 0;
}