[BOJ15999] 뒤집기

격자판 초기 상태로 가능한 경우의 수를 1,000,000,007로 나눈 나머지

• N x M 행렬
• 격자를 누르면 자신을 포함해 연결된 칸 색이 반전됨
• 연결의 조건 : 두 격자 사이를 같은 색이면서 변을 공유
• 최종 상태로 초기 상태 유추
• 두 격자판의 상태가 다른 경우 : 같은 위치의 격자의 색이 다른 경우가 존재할 때

입력

• 첫 줄에 행 열 : N, M (1 <= N, M <= 2,000)
• N개의 줄에 각 격자의 색을 나타내는 문자열 (b, w)

출력

• 첫 줄에 격자의 초기 상태로 가능한 경우의 수를 1,000,000,007(10^9+7)로 나눈 나머지

설계

• 격자를 누르면 연결된 격자의 색이 같이 변하므로, 현재 상태에 특정 격자와 인접해있는 격자의 색이 다르면 ex) bw 이 상태는 초기상태와 같다
• 따라서 다른 색이 인접해있는 경우가 아닌 격자들은 모두 색이 바뀔 수 있는 상태
• 총 격자 수 - 인접한 격자가 색이 다른 격자의 수
• 구한 다음에 2 제곱 후 모듈러 연산

피드백

• BFS를 이용해서 인접한 경우가 색이 다른 경우를 체크했는데, 자꾸 틀림
• wbbw 와 같은 경우에서 세 번째 격자인 b를 체크 못 해주는 상황이 발생
(두 번째 b가 세 번째 b 탐색할 때 색이 같아서 방문 체크만하고 카운팅 안 함)
• 그냥 쉽게 각 격자 모두 탐색 2중 루프 돌리고 사방 체크 후 다른 격자 있으면 카운팅 하는 방식 사용
• 그래도 답이 계속 틀림
• 아무래도 배열이 크기 때문에 제곱할 때 오버플로우가 생긴 듯 함
• 제곱 연산을 pow함수가 아닌 for문으로 구현하고 루프를 돌 때마다 나머지(모듈러) 연산도 함께 실행

How I solved(click to github)

---

ref :
BOJ15999