[백준] 10026번 적록색약

문제: 10026번: 적록색약

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;


int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int BFS(int n, vector<vector<char>> board, vector<vector<int>> visit) {
    int answer = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (visit[i][j] == 1) continue;

            answer++;
            char curColor = board[i][j];
            queue<pair<int, int>> nexts;
            nexts.push(make_pair(i, j));
            visit[i][j] = 1;

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

                for (int c = 0; c < 4; c++) {
                    int nx = cur.first + dx[c];
                    int ny = cur.second + dy[c];

                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (board[nx][ny] != curColor || visit[nx][ny] == 1) continue;

                    nexts.push(make_pair(nx, ny));
                    visit[nx][ny] = 1;
                }
            }
        }
    }

    return answer;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vector<vector<char>> nonBoard(n);
    vector<vector<char>> dalBoard(n);
    vector<vector<int>> nonPVisit(n);
    vector<vector<int>> dalPVisit(n);
    

    for (int i = 0; i < n; i++) {
        nonBoard[i] = vector<char>(n);
        dalBoard[i] = vector<char>(n);
        nonPVisit[i] = vector<int>(n);
        dalPVisit[i] = vector<int>(n);

        for (int j = 0; j < n; j++) {
            cin >> nonBoard[i][j];

            if (nonBoard[i][j] == 'G')
                dalBoard[i][j] = 'R';
            else
                dalBoard[i][j] = nonBoard[i][j];
        }
    }

    int dalPerson = BFS(n, dalBoard, dalPVisit);
    int nonPerson = BFS(n, nonBoard, nonPVisit);
    
    cout << nonPerson << " " << dalPerson;

   
    return 0;
}

 

그냥 BFS 를 2번 돌리면 되는 쉬운 문제다. 적록색약인 경우와 아닌 경우로 나눠서 BFS 를 돌리면 된다. BFS 를 따로 만들어서 2번 돌렸다. 함수 따로 안 만들면 코드가 너무 길어져서 그냥 만들었다.

 

적록색약인 경우에는 board 에 값을 채울 때 G 를 R 로 취급해주면 된다. 이렇게만 해주고 그냥 바로 BFS 돌리면 된다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x09강 - BFS

[실전 알고리즘] 0x09강 - BFS