백준 - 3085번(사탕 게임)

문제 출처: https://www.acmicpc.net/problem/3085

문제

• 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

• 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

• 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private String[][] matrix;

    public static void main(String[] args) throws IOException {
        // 탐색은 좌측 탐색, 우측 탐색. swap 후 최대값을 찾는다.
        // swap 대상을 찾으면 swap을 진행
        Main main = new Main();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        main.matrix = new String[N][N];
        int result = 0;
        for (int i = 0; i < N; i++) { // 배열에 저장
            main.matrix[i] = reader.readLine().split("");
        }
        // 제일 처음 상태 먼저 계산
        if (main.findMax(N) == N) {
            System.out.println(N);
        } else {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N - 1; j++) {
                    // 행에서 다른게 있을 경우 swap
                    if (main.matrix[i][j] != main.matrix[i][j + 1]) {
                        main.swap(i, j, i, j + 1);
                        result = Math.max(result, main.findMax(N));
                        main.swap(i, j, i, j + 1);
                    }
                }
            }

            for (int j = 0; j < N; j++) {
                for (int i = 0; i < N - 1; i++) {
                    // 열에서 다른게 있을 경우 swap
                    if (main.matrix[i][j] != main.matrix[i + 1][j]) {
                        main.swap(i, j, i + 1, j);
                        result = Math.max(result, main.findMax(N));
                        main.swap(i, j, i + 1, j);
                    }
                }
            }
            System.out.println(result);
        }
    }

    private int findMax(int size) {
        // 배열을 둘러보며 최대치 찾기
        int result = 0;
        for (int i = 0; i < size; i++) {
            // 행
            int count = 1;
            for (int j = 0; j < size - 1; j++) {
                if (matrix[i][j].equals(matrix[i][j + 1])) {
                    count++;
                } else {
                    result = Math.max(result, count);
                    count = 1;
                }
            }
            result = Math.max(result, count);
        }

        for (int j = 0; j < size; j++) {
            // 열
            int count = 1;
            for (int i = 0; i < size - 1; i++) {
                if (matrix[i][j].equals(matrix[i + 1][j])) {
                    count++;
                } else {
                    result = Math.max(result, count);
                    count = 1;
                }
            }
            result = Math.max(result, count);
        }
        result = result == 1 ? 0 : result;
        return result;
    }

    private void swap(int x1, int y1, int x2, int y2) {
        String temp = matrix[x1][y1];
        matrix[x1][y1] = matrix[x2][y2];
        matrix[x2][y2] = temp;
    }

}

• 이 문제는 상당히 오랜 시간이 소요되었다. 어떻게든 좋은 로직을 구현해보고자 여러 방식으로 접근하였으나 결국 성공하지 못하고 다른 분들의 로직을 참고하였다.
• 내가 참고한 분의 로직은 단순했다. 모든 요소를 다 swap 하고 그때마다 전체 배열을 탐색하며 최대값을 찾는 것이다.
• 약간 멘붕이 왔다. 이것이 brute-force인가...
• 때론 이런 무차별적 공격법이 유용함을 깨달았다.
• 참고한 로직에서 모든 배열 요소를 swap하는 것이 아니라, 인접한 값이 다른 것들만 swap하여 탐색하는 방식으로 추가하여 구현하였다.