BOJ 10026 c++ 적록색약

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

 

#include <bits/stdc++.h>
using namespace std;

string str;
int n;
char board[105][105];
int vis[105][105];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int bfs(char c){
  int cnt=0;
  for(int i=0; i<105;i++)
    fill(vis[i],vis[i]+105,0);
  queue<pair<int,int>> Q;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(board[i][j]!=c) continue;
      if(vis[i][j]==1) continue;
      vis[i][j]=1;
      Q.push({i,j});
      cnt++;
      while(!Q.empty()){
        auto cur=Q.front(); Q.pop();
        // cnt++;
        for(int dir=0; dir<4; dir++){
          int nx=cur.first+dx[dir];
          int ny=cur.second+dy[dir];
          if(nx<0||nx>=n||ny<0||ny>=n) continue;
          if(board[nx][ny]!=c) continue;
          if(vis[nx][ny]==1) continue;
          vis[nx][ny]=1;
          Q.push({nx,ny});  
        }
      }
    }
  }
  return cnt;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;

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

  cout<<bfs('R')+bfs('G')+bfs('B')<<' ';
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(board[i][j]=='G') board[i][j]='R';
    }
  }
  cout<<bfs('R')+bfs('B');
}

위에 있는 내가 제출한 풀이의 경우는, 각각의 R, G, B 일때의 경우의 수들을 따로따로 나타낼 수 있도록 만든 풀이인데, 다른 풀이를 보다보니 이런식으로 해결하지 않고, 그냥 한번에 구분지어저 있는 영역들의 갯수를 바로 출력하도록 하는 풀이를 볼 수 있었다. 

 

// Authored by : seeys
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/99a676d859f54fa0944f81f94ade04a3
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
char board[101][101];
bool vis[101][101];
int n;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; 

void bfs(int i, int j) {
  queue<pair<int, int>> Q;
  Q.push({ i,j });
  vis[i][j] = 1;
  while (!Q.empty()) {
    auto cur = Q.front(); Q.pop();
    for (int dir = 0; dir < 4; dir++) {
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
      if (vis[nx][ny] == 1 || board[i][j] != board[nx][ny]) continue;
      vis[nx][ny] = 1;
      Q.push({ nx,ny });
    }
  }
}

int area(){
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!vis[i][j]) {
        cnt++;
        bfs(i, j);
      }
    }
  }
  return cnt;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> board[i][j];
    }
  }
  int not_g = area(); //적록색약이 아닌사람

  // 적록색약인 사람을 구하기위한 방문배열 초기화
  for(int i = 0; i < n; i++)
    fill(vis[i], vis[i]+n, false);
  
  // 적록색약은 초록과 빨강을 구분 못하므로 초록이면 빨강으로 바꿔줌
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (board[i][j] == 'G')
        board[i][j] = 'R';
    }
  }

  int is_g = area(); //적록색약인 사람
  cout << not_g << " " << is_g;
  return 0;
}

이 풀이에서는 if(board[i][j]!=board[nx][ny]) continue; 라는 조건으로 bfs를 돌려서, 해당 함수를 통해서 한번에 다른 영역들에 대해서 bfs를 돌면서, 해당 영역이 주변에 있는 영역들과 다른 영역이라면 cnt++ 을 시켜주어서 R 로 이루어져있던, G로 이루어져 있던, B로 이루어져 있던 모두 cnt++ 가 되도록 해서 영역들에 대해서 딱 영역이 다른 부분들에 대해 판별해줄 수 있는 함수를 작성했다. 

이런 식의 풀이가 문제가 요구하는 사항에 확실하게 군더더기 없이 부합하는 풀이일 수 있겠다는 생각이 든다. 

 

또한  문제에서 입력으로 주어지는 값에서, 

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

위에서 볼 수 있는 바와 같이, 모두 붙어있는 형태로 주어지는데, 이렇게 붙어있는 경우 string으로 받아야 한다고 생각했는데, 다른 사람의 풀이에서 볼 수 있듯이 다 붙어 있더라도 char로 선언되어 있는 배열에 각각 하나의 요소씩 받아서 값들을 대입해줄 수 있다는 것을 알고 있으면 다음에 이런식으로도 board 를 초기화 해줄 수 있을것 같다. 물론 내가 수행한 방식처럼 하더라도 문제될것 없다. 

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