[SW Expert] 6731. 홍익이의 오델로 게임

생각

Github - https://github.com/hellojdh/Code/blob/master/src/swexpert/d4/Q6731.java

오델로의 판이 주어진다. 한 칸을 선택하면 해당 칸의 가로줄 세로줄이 모두 뒤집힌다.
초기 상태(모두 흰색)로 만들 경우 뒤집어야하는 최소 칸수를 선택하여라.

처음 생각

몇 몇 질문들을 보면서 글을 작성해본다.

문제를 보면 우선적으로 드는 생각은 DFS를 이용하는 방법이다. 조합을 만들거나 DFS를 통해 검은돌이나 흰돌을 선택해 나가면서 진행을 하고자하는 생각이 무럭무럭 든다.

▶ 하지만 배열이 최대 1000*1000 이다. 따라서 모든 경우를 따져주기에는 시간이 많이 부족하다. 조합을 만들어 주는 경우도 몇 십개만 되도 많은 시간이 걸리므로 모든 경우를 따져주는 생각을 버려야했다.

다음 생각

그럼 시간을 어떻게 줄일 수 있을까? 고급 알고리즘을 모르는 상태에서 생각나는건

1) DP

2) 수학적인 방법으로 접근

3) 규칙 찾기

정도를 생각해 볼 수 있다.

▶ 오델로 문제의 경우는 수식 풀이가 아니므로 DP와 수학 방법을 제쳐두고 규칙을 찾아보자는 생각을 하였다.

다다음 생각

과연 규칙은 어떻게 찾아야 할까? 모든 오델로 판의 상태에서 적용이 가능해야 하기때문에 단계별로 공통점을 찾고자 하였다. 4칸의 오델로 상태를 예로들어보자.

▶ 초기 상태에서 그냥 아무칸이나 선택했을 경우의 판은 다음과 같다.

오델로1

▶ 거기서 그냥 아무칸이나 또 선택했을 경우의 판은 다음과 같다.

오델로2

▶ 또 이어서 그냥 아무칸이나 또 선택했을 경우의 판은 다음과 같다.

오델로3

▶ 딱보고 공통점이 보인다면 이미 상당한 실력자임이 틀림없을 것이다. 더군다나 표시한다고 빨간 펜까지 더해져서 지저분한 저 그림을 보면서 드는 생각은 없을 수 도 있다...

▶ 그렇다면 어떻게 해야할까? 위의 과정을 거치면서 했던 일은 한 가지이다. v표시를 한 곳을 선택하면 그곳의 가로줄과 세로줄을 뒤집어 주었다. 즉, v 표시를 한 곳을 기점으로 주변의 상태가 변한다는 것이다.

다다다음 생각

오델로.. 판.. 검정색.. 흰색... 한 곳을 기점으로 상태가 바뀐다.. 수식을 쓸 수도 없고 멀 해볼 수도 없고 단순히 변화의 중심을 기점으로 개수를 세기 시작했다. 다시 위 사진 3개를 보면서 개수를 세어보자. 초기상태에서 변화하는 과정을 찾아내는게 문제이므로 중점을 기준으로 바뀌는 검은돌을 세아렸다.

▶ 첫번째

오델로4

▶ 두번째

오델로5

▶ 세번째

오델로6

▶ 앞에서 뒤집었던걸 까먹었을 수도 있으니 개수를 센 각 사진에 뒤집힘을 표시해보자.

오델로7

▶ 놀랍게도 오델로를 뒤집은 칸은 주변 검은색 개수가 홀수개인 것을 볼 수 있었다.

▶ 조금 생각을 해보면 주어지는 N이 무조건 짝수이므로 가로 세로가 겹치는 구간인 뒤집은 부분은 홀수의 개수를 얻을 수 밖에 없다!!!!!

다다다다음 생각

이제 오델로를 뒤적거리며 개수를 세어주어야한다. 입력이 최대 1000*1000이므로 한칸 한칸 모든 칸을 이중 반복문으로 확인을 하면 최대값일 경우만 따져도 엄청난 시간이 걸리게된다. 따라서 다음과 같이 해결하였다.

▶ 같은 가로줄 한 줄의 검은돌의 개수는 모두 같다.

▶ 같은 세로줄 한 줄의 검은돌의 개수는 모두 같다.

▶ 즉, 가로줄을 한 번만 탐색해서 돌의 개수를 모두 찾은 뒤, 해당 가로줄의 개수 배열에 모두 같은 값을 넣어 주었다.(세로줄도 마찬가지이다.)

다다다다다음 생각

앞서 각 가로줄과 세로줄은 모두 같은 개수를 가지고 있으므로, 시간을 좀 더 줄여보기위해서 일차 배열 2개(garo[n],sero[n] 크기)를 만들어서 입력을 받으면서 바로 개수를 카운트 해주었다.

▶ 가로 세로의 합계를 계산할 때, 해당 칸이 흰색이냐 검은색이냐도 판단을 해주어야한다. 검은색일 경우는 카운트가 한 번 중복되서 들어가기 때문에 -1을 해주어야한다.

방안

1) Java 풀이

package swexpert.d4;
 
import java.io.*;
 
public class Q6731 {
    static int n;
    static char[] garo,sero;
    static boolean[][] arr;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int tc = Integer.parseInt(br.readLine());
 
        for(int z=1;z<=tc;z++){
            n = Integer.parseInt(br.readLine().trim());
            arr = new boolean[n][n];
            garo = new char[n];
            sero = new char[n];
            // W = false, B = true
            for(int i=0;i<n;i++){
                String t = br.readLine();
                // 입력 하면서 가로 세로 개수 세기
                for(int j=0;j<n;j++) {
                    if (t.charAt(j) == 'B') {
                        arr[i][j] = true;
                        garo[i]++;
                        sero[j]++;
                    }
                }
            }
 
            int result = 0;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    int t = garo[i]+sero[j];
                    if(arr[i][j]){
                        // 검은색일 경우 -1해주기
                        if(--t%2!=0) result++;
                    }else{
                        if(t%2!=0) result++;
                    }
                }
            }
            bw.write("#"+z+" "+result+"\n");
        }// end of tc
        bw.flush();
    } // end of main
}// end of class