[1018] 체스판 다시 칠하기 - C++

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

1018번: 체스판 다시 칠하기

이게 실버 4라고? ㅎ...

 

풀이를 시작하기전 말할 것이 있다면 나는 좀 이상하게 푼 것 같다.... 뭐지

일단 시작 하겠다.

 

---

풀이

( 주의! ) 처음에 문제 이해를 잘못한 나머지 항상 B 일 때만 계산했다.
왼쪽 위가 B로 시작할 때, W로 시작할 때 둘 다 계산해줘야 한다.

가장 먼저 우리가 해야 하는 8 x 8로 자를 수 있는 모오오든 경우의 수를 구해야 한다.

 

8 x 8로자를 수 있는 모오오든 경우의 수 CODE

for(int i = 0; i <= n-8; ++i){
    for(int j = 0; j <= m-8; ++j){
      // { 실행 로직.... }
    }
  }

그다음 해야 하는 것은 BFS를 구현하자

 

BFS CODE

필요한 것

• 큐
• 방문표시 배열
• 새로운 8 x 8 배열 ( board2 )

int bfs(int i, int j, char c){
  for(int k = 0; k < 8; ++k)
    for(int w = 0; w < 8; ++w)
      board2[k][w] = board[i + k][j + w];

// 가장 처음이 보내준 문자와 다르다면 카운트를 1부터 시작 
  int cnt = (board2[0][0] != c)?1 : 0;
  
  //큐 생성
  queue<pair<int, int>> q;
  q.push({0, 0});
  dist[0][0] = 1;
  //보드에 문자 저장 후 시작
  board2[0][0] = c;

  while(!q.empty()){
    int x, y;
    tie(x, y) = q.front(); q.pop();
    
    //네 방향 검사 for문
    for(int dir = 0; dir < 4; ++dir){
      int nx = x+dx[dir];
      int ny = y+dy[dir];
      
      //배열 밖으로 나가거나 이미 방문 했던 곳이라면 continue
      if(OOB(nx, ny) || dist[nx][ny])continue;
      
      //   [B]
      //[W][B][B]
      //   [B]
      // 만약 간운데와 현재 인덱스의 문자가 같다면 바꿔준 후 cnt++
      if(board2[x][y] == board2[nx][ny]){
        board2[nx][ny] = (board2[x][y] == 'B')? 'W' : 'B';
        cnt++;
      }
      //다음 인덱스 큐에 Push
      q.push({nx, ny});
      dist[nx][ny] = 1;
    }
  }
  //8x8 보드 탐색을 끝내고 방문 표시 배열을 다시 0으로 초기화 해준다
  memset(dist, 0, 9*9*sizeof(bool));
  return cnt;
}

나는 이렇게 풀었다. 정말 비효율 적인 풀이다. 그렇지만... 나의 역량인걸....

 

Main 부분 CODE

int main(){
  init();
  cin >> n >> m;
  for(int i = 0; i < n; ++i)
    cin >> board[i];
  
  for(int i = 0; i <= n-8; ++i)
    for(int j = 0; j <= m-8; ++j)
      ans = min({ans, bfs(i, j, 'W'), bfs(i, j, 'B')});
  cout << ans;
  return 0;
}

아까 봤던 모든 경우의 수를 도는 이중 for문이 여기 사용된다.

---

전체 CODE

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, m, ans = 2E+9;

string board[51];
char board2[9][9];
bool dist[9][9];

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

bool OOB(int nx, int ny){
  return nx < 0 || nx >= 8 || ny < 0 || ny >= 8;
}

int bfs(int i, int j, char c){
  for(int k = 0; k < 8; ++k)
    for(int w = 0; w < 8; ++w)
      board2[k][w] = board[i + k][j + w];

  int cnt = (board2[0][0] != c)?1 : 0;
  queue<pair<int, int>> q;
  q.push({0, 0});
  dist[0][0] = 1;
  board2[0][0] = c;

  while(!q.empty()){
    int x, y;
    tie(x, y) = q.front(); q.pop();
    for(int dir = 0; dir < 4; ++dir){
      int nx = x+dx[dir];
      int ny = y+dy[dir];
      if(OOB(nx, ny) || dist[nx][ny])continue;
      if(board2[x][y] == board2[nx][ny]){
        board2[nx][ny] = (board2[x][y] == 'B')? 'W' : 'B';
        cnt++;
      }
      q.push({nx, ny});
      dist[nx][ny] = 1;
    }
  }
  memset(dist, 0, 9*9*sizeof(bool));
  return cnt;
}

int main(){
  init();
  cin >> n >> m;
  for(int i = 0; i < n; ++i)
    cin >> board[i];
  for(int i = 0; i <= n-8; ++i)
    for(int j = 0; j <= m-8; ++j)
      ans = min({ans, bfs(i, j, 'W'), bfs(i, j, 'B')});
  cout << ans;
  return 0;
}

 

문제를 풀며

이게 맞나 싶었다.

실버 4라는 티어를 얕잡아 보고 "어? 이거 설계 안 하고 바로 구현 가능 할 듯!"이라고 생각한 내가 부끄럽다. 

내 코드는 정말 비효율 적이기에 배우고 싶은 아이디어를 사용하여 푸신 분의 블로그 링크를 붙여 놓겠다.

https://cryptosalamander.tistory.com/13

[백준 / BOJ] - 1018번 체스판 다시 칠하기 C++ 풀이

어찌 이런 생각을 했는가..... 미쳐 따이