[백준][bfs] 10026 적록색약 c++ 구현

목차

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

10026번: 적록색약

문제

 

 

문제 구현 방향

bfs탐색이 어짜피 O(N^2)이고 범위가 적어 시간을 생각하지 않고 전처리를 해주어 정상인일 때와 

적록색약일때를 탐색 했다. 적록색약은 적색과 초록색을 같은 색으로 만들어 주고 탐색해주면 된다.

 

 

 

코드 구현

#include <iostream>
#include <vector>
#include<queue>

using namespace std;

char board[101][101];
int visit[101][101] = { 0 };
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int N;

void bfs(int start_x, int start_y) {
    char direct = board[start_y][start_x];
    queue<pair<int, int>> q;
    visit[start_y][start_x] = 1;
    q.push(make_pair(start_x, start_y));
    while (!q.empty()) {
       int x = q.front().first;
       int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {  //누적하면 틀림 주의 =>  x= x+ dx[i] 이렇게 하면 안됨
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x >= 0 && new_x <= N - 1 && new_y >= 0 && new_y <= N - 1) {  
          
                if (board[new_y][new_x] == direct && visit[new_y][new_x] == 0) {
                    visit[new_y][new_x] = 1;
                    q.push(make_pair(new_x, new_y));

                }
      
            }
        }
    }
}

int main()
{
    int i,j, cnt1=0, cnt2=0;
 
    cin >> N;

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            cin>> board[i][j];
            }
       }
    
    for (i = 0; i < N; i++) {   //정상인 탐색시작
        for (j = 0; j < N; j++) {
            if (visit[i][j] == 0) {
                bfs(j, i);
                cnt1++;
            }
        }
    }

    for (i = 0; i < N; i++) {  //방문 초기화 및 적록색약을 위한 전처리
        for (j = 0; j < N; j++) {
            visit[i][j] = 0;
            if (board[i][j] == 'R') {  ///적색 초록색 같게 만듬
                board[i][j] = 'G';
            }
        }
    }
    
    for (i = 0; i < N; i++) {   //적록색약 탐색시작
        for (j = 0; j < N; j++) {
            if (visit[i][j] == 0) {
          
                bfs(j, i);
                cnt2++;
            }
        }
    }

    cout << cnt1 << " " << cnt2;

}