BOJ 15999 - 뒤집기

www.acmicpc.net/problem/15999

15999번: 뒤집기

 

처음에 문제를 봤을때는, 이전 상태의 가능한 경우의 수를 모두 찾아내야 하니

브루트포스를 쓰는건가 싶었다.

 

오랫동안 문제 자체를 제대로 이해못하고 있다가, 

공식 홈페이지 해설을 보고 문제를 어떻게 풀어야 될지 방향성을 잡았다

tech.kakao.com/2018/09/12/code-festival-2018-round-2/

코드 페스티벌 2018 본선 이야기

 

위의 해설대로라면, 서로 같은 색상을 갖는 타일의 갯수를 찾아내야 했다.

탐색을 어떻게 할까 고민을 하다가, 인접한 격자(상하좌우 4방향)만 비교하면 되므로, BFS 나 DFS 는 아닐것 같았고,

N과 M 의 최대 크기가 2000 이므로, 2000 * 2000 * 4 를 하더라도 시간 초과가 나지 않아서 삼중포문을 사용했다.

 

그런데 문제는, 중복된 경우를 어떻게 배제할지에 대해서 많이 틀렸다

처음엔 dfs,bfs 에서 자주 나오는 bool visited[][] 이중 배열을 만들어서 방문 처리를 해봤다가

겹치는 격자가 처리가 안되서 틀렸고, 여러가지 써보다가 틀렸다.

 

처음엔 서로 같은 색상을 찾는데 중점을 두다가 나중엔 다른게 나오면 

전체 타일 수에서 빼는 것으로 바꿔서 처리했다.

( N * M - cnt )

 

- c++

#include <iostream>
 
#define MAX 2001
 
using namespace std;
 
const int MOD = 1000000007;
int n, m;
char adj[MAX][MAX];
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> m;
    
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < m; ++j) 
            cin >> adj[i][j];
 
    int cnt = 0;
    // 2000 * 2000 * 4 => 시간내에 가능 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < 4; ++k) {
                int ny = i + dy[k], nx = j + dx[k];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if (adj[i][j] != adj[ny][nx]) {
                    cnt++;
                    break;
                }
            }
        }
    }
    
    int answer = 1;
    for (int i = 0; i < (n * m) - cnt; ++i) 
        answer = (answer * 2) % MOD;
    
    cout << answer;
    
    return 0;
}