[백준] 10026번 - 적록색약 (골드 5)

문제

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

10026번: 적록색약

 

---

 

접근 방식

• 기본 Map과 색약 Map을 만들어 BFS로 구역을 나눠줌
• 틀렸습니다. 코드와 정답 코드 차이

// 틀린 코드
if (map_visit[i][j] == 0) {
	q.push({i, j});
    visit_value++;
}

// 정답 코드
if (map_visit[i][j] == 0) {
	q.push({i, j});
	map_visit[i][j] = ++visit_value;
}

---

 

코드

#include <iostream>
#include <cstring>
#include <utility> 
#include <queue> 

using namespace std;

void func_10026_bfs(queue<pair<int, int>> q, char **_map, int **visited, int visit_value, int n) {
    pair<int, int> tmp_coord;
    int _x, _y;
    char tmp_color;
    int direct[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

    while (!q.empty()) {
        tmp_coord = q.front();
        tmp_color = _map[tmp_coord.first][tmp_coord.second];
        q.pop();

        for (int i = 0; i < 4; i++) {
            _x = tmp_coord.first + direct[i][0];
            _y = tmp_coord.second + direct[i][1];

            if (_x >= n || _x < 0)
                continue;
            
            if (_y >= n || _y < 0)
                continue;

            if (visited[_x][_y] != 0)
                continue;

            if (_map[_x][_y] != tmp_color)
                continue;

            visited[_x][_y] = visit_value;
            q.push({_x, _y});
        }
    }
}

int main() {
    queue<pair<int, int>> q;
    int visit_value, map_max, map_rg_max;
    
    int n;
    cin >> n;

    char** map_origin = new char* [n];
    char** map_rg = new char* [n];
    int** map_visit = new int* [n];
    int** map_rg_visit = new int* [n];

    for (int i = 0; i < n; i++) {
        map_origin[i] = new char[n];
        map_rg[i] = new char[n];
        map_visit[i] = new int[n];
        map_rg_visit[i] = new int[n];

        memset(map_visit[i], 0, sizeof(int) * n);
        memset(map_rg_visit[i], 0, sizeof(int) * n);
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++) {
            cin >> map_origin[i][j];
            
            if (map_origin[i][j] == 'R')
                map_rg[i][j] = 'G';
            else
                map_rg[i][j] = map_origin[i][j];
        }
    }

    visit_value = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_visit[i][j] == 0) {
                q.push({i, j});
                map_visit[i][j] = ++visit_value;
            }

            func_10026_bfs(q, map_origin, map_visit, visit_value, n);
        }
    }


    while (!q.empty()) {
        q.pop();
    }

    visit_value = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_rg_visit[i][j] == 0) {
                q.push({ i, j });
                map_rg_visit[i][j] = ++visit_value;
            }

            func_10026_bfs(q, map_rg, map_rg_visit, visit_value, n);
        }
    }

    map_max = 0;
    map_rg_max = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_max < map_visit[i][j]) {
                map_max = map_visit[i][j];
            }

            if (map_rg_max < map_rg_visit[i][j]) {
                map_rg_max = map_rg_visit[i][j];
            }
        }
    }
    
    cout << map_max << " " << map_rg_max << "\n";
    
    return 0;
}

---

 

결과