[15999번] 뒤집기

문제

어느 날, 네오는 길을 걷다가 격자판 하나를 주웠다. 그 격자판은 N 행 M 열로, 각 격자는 흰색 또는 검은색으로 칠해져 있다.

네오는 이 격자판에는 분명 엄청난 비밀이 숨겨져 있을 것이라고 생각해 나중에 해독을 시도해 보기로 하였다. 아래 그림은 격자판 상태의 예시이다.

네오가 잠시 외출한 사이, 프로도는 네오의 격자판을 이리저리 살펴보았다. 얼마 뒤, 하나의 격자를 누르게 되면 자신을 포함해 그 격자와 연결된 모든 칸들의 색이 반전된다는 사실을 관찰할 수 있었다. 여기서, 두 격자가 연결되었다는 것은 두 격자 사이를 서로 같은 색이면서 변을 공유하는 격자들로만 이동하여 오갈 수 있다는 것을 뜻한다. 집으로 돌아온 네오는 프로도가 격자판의 상태를 바꿔버렸다는 것을 알고 좌절했다. 하지만 최종 상태를 알고 있기 때문에, 초기 상태를 추측할 수 있을 것이라는 희망을 가지기로 했다.

프로도는 격자판을 0번 이상 눌렀다(아직 한 번도 누르지 않은 상태일 수도 있다). 현재 각 격자의 색깔이 주어졌을 때, 격자판의 초기 상태로 가능한 경우의 수를 1,000,000,007(10^9 + 7)로 나눈 나머지를 구하여라. 두 격자판의 상태가 다르다는 것은, 같은 위치의 격자의 색이 다른 경우가 존재할 때로 정의한다.

 

입력

첫 줄에 격자판의 행의 수 N 과 열의 수 M 이 주어진다. (1 ≤ N, M ≤ 2,000)

둘째 줄부터 N 개의 줄에 걸쳐 현재 각 격자의 색을 나타내는 문자열이 주어진다.

N 개의 줄 중에서 i 번째 줄의 j 번째 문자는 i 행 j 열 격자의 색을 나타내며, 'B'인 경우 검은색, 'W'인 경우 흰색임을 나타낸다.

 

출력

첫 줄에 격자의 초기 상태로 가능한 경우의 수를 1,000,000,007(109 + 7)로 나눈 나머지를 출력한다.

 

나의 답

#include <bits/stdc++.h>

using namespace std;

vector<vector<bool>> table;
int n,m;

void input() {
    cin >> n >> m;
    string temp;
    for(int i = 0; i < n; ++i) {
        cin >> temp;
        vector<bool> temp_table;
        table.push_back(temp_table);
        for(int j = 0; j < temp.size(); ++j) {
            if(temp[j]=='W')
                table[i].push_back(0);
            else if(temp[j]=='B')
                table[i].push_back(1);
        }
    }
}

bool around_same(int i, int j) {
    int result = 0;
    if(((i-1>=0&&table[i-1][j]==table[i][j])||(i-1<0))&&
       ((j-1>=0&&table[i][j-1]==table[i][j])||(j-1<0))&&
       ((i+1<n &&table[i+1][j]==table[i][j])||(i+1>=n))&&
       ((j+1<m &&table[i][j+1]==table[i][j])||(j+1>=m)))
       return true;
    else
        return false;
}

long long power(long long a, long long b, long long c) {
    long long pow_result;

    if (b==1) {
        pow_result = a%c;
    }
    else if (b%2==0) {
        pow_result = ((power(a, b/2, c) % c) * (power(a, b/2, c) % c)) % c;
    }
    else {
        pow_result = ((power(a, b/2, c) % c) * (power(a, b/2 + 1, c) %c)) % c;
    }

    return pow_result;
}

void calc() {
    int result = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(around_same(i, j)==true)
                ++result;
        }
    }
    cout << power(2, result, 1000000007) << endl;
}

int main(void) {
    input();
    calc();
    return 0;
}

문제 예시를 통해 이해해보자. 왼쪽 위 칸만 하얀 색일 때가 마지막 상태라면 그 왼쪽 위 칸은 무조건 하얀 색이고 이와 접한 아이들은 검정색이어야 한다. 즉, 여기서 영향을 받지 않는 칸은 마지막 상태일 때 인접한 칸들이 모두 자기와 같은 색인 오른쪽 아래 칸밖에 없다. 따라서 예제에서 가능한 경우의 수는 오른쪽 아래 칸이 검정색일 때와 흰 색일 때 두 가지 경우이다. 같은 원리로 다른 경우도 똑같이 적용된다. 즉, 인접한 칸들이 모두 같은 색인 칸은 검정색 흰 색 둘 중 선택 가능하다. 따라서 처음 상태가 될 수 있는 모든 경우의 수를 구하려면 인접한 칸들이 모두 같은 색인 칸 수를 구해 2^n을 해주면 된다.

 

출처

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

15999번: 뒤집기