JArchive 프로그래밍 일기

문제

적록색약 백준 10026

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, nor, abnor;
int arr[102][102];
bool vis[102][102] = {false};
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

bool checkrange(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < n);
}

void bfs(int i, int j, int target){
  queue<pair<int,int>> qu;

  vis[i][j] = true;
  qu.push({i, j});

  while(!qu.empty()){
    int cx = qu.front().X;
    int cy = qu.front().Y;
    qu.pop();

    for(int i = 0; i < 4; i++){
      int nx = dx[i] + cx;
      int ny = dy[i] + cy;

      if(!checkrange(nx, ny) || (arr[nx][ny]!=target) || vis[nx][ny]) continue;
      vis[nx][ny] = true;
      qu.push({nx,ny});
    }
  }
}

void input(){
  cin >> n;

  string str = "";

  for(int i = 0; i < n; i++){
    cin >> str;
    for(int j = 0; j < n; j++){
      switch(str[j]){
        case 'R':
          arr[i][j] = 1; break;
        case 'G':
          arr[i][j] = 2; break;
        case 'B':
          arr[i][j] = 3; break;
      }
    }
  }
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  input();

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

  // R -> G 으로 변경.
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(arr[i][j] == 1) arr[i][j] = 2;
    }
  }

  // 방문배열 초기화
  for(int i = 0; i < n; i++) fill(vis[i], vis[i]+n,0);

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

  cout << nor << ' '<< abnor;
  return 0;
}

리뷰

유기농 배추 문제와 비슷한 기본적인 bfs 문제였다.

R, G, B 문자는 숫자로 변경해서 저장했다. 나는 string을 이용해서 한 줄 받은다음에, 하나씩 int로 넣었는데.
다른분 코드를 보니 int 그대로 저장하는 방법도 있었다.

코드 순서는 아래와 같다.

1. 이중 for문을 돌면서, 방문하지 않은 칸인 경우 bfs를 시작한다. 이 때, 파라미터로 현재 칸의 색깔숫자를 넘긴다.
2. 현재 칸의 색깔 숫자와 같으면서도 미방문인 칸을 큐에 push하면서 bfs를 수행한다.
3. 이렇게 bfs를 돌리면서 vis배열이 꽉 차면 적록색약이 아닌사람이 볼 떄의 공간개수가 nor에 저장된다.
4. 적록색약인 경우 1인 칸과 2인칸이 똑같이 보이도록 1을 2로 바꿔준다. 이중 for문을 돈다.
5. 방문 배열을 초기화한다.
6. 현재 칸의 색깔 숫자와 같으면서도 미방문인 칸을 큐에 push하면서 bfs를 수행한다. 이 때 bfs를 도는 횟수가 abnor에 저장된다. ( abnor == 적록색약인 사람이 구분하는 영역의 개수)