브루트포스. 사탕게임

문제

애니팡 같은 문제로, 서로 다른 알파벳을 바꿔서 그 행이나 열 중 가장 크게 먹을수있는 최대의 수를 구하는 문제다.

해결방향성

가장 크게 먹을 수 있는 최대 경우의 수를 모두 찾아야한다. 따라서 첫번째 원소부터 행과 열을 확인하는 작업을 반복한다.
처음에는 기준점을 color로 삼아 0번째 원소부터 색깔이 같으면 count++ 하면서 진행하고, 색깔이 다를때 가로 기준으로 상,하에 같은수를 찾고, 세로 기준으로는 좌,우로 같은 수를 찾는 방식을 택했다.
하지만, 이 문제를 해결하기 위해서는 경우의 수가 있는데,
1. 연속하는 수가 같은 숫자인경우 -> 이경우는 문제없다
2. 끝수가 다른 경우인경우 -> 이경우도 문제없다.
3. 처음 수가 다른 경우 -> 상하 or 좌우에 같은 수가있는경우
3-1. 아예 같은 수가 없는 경우 -> 이 경우는 따로 boolean으로 처리해주었다.
하지만, 이 경우를 모두 만족하는 경우는 찾기 어려워 다른 방법으로 해결해야했다.
따라서, 한번에 모두 행과 열을 동시에 해결하기보다, 행, 열을 따로 나누어 상하, 좌우를 바꿔서 영향을 주는 행과 열을 처리하는 방향으로 잡았다.
첫째로,
좌, 우로 바꾸는 경우이다. 이 경우는 두 열과, 한 행이 영향을 받는다. 따라서, 바꾸고 난후, 연속된 개수를 두 열, 한 행 모두 카운트해서, 가장 큰값을 저장해준다.
둘째로,

상, 하로 바꾸는 경우이다. 상, 하로 바꾸면 두 행, 한 열이 영향을 받으므로, 이 세경우에 대해서 가장 큰 경우를 구해준다.
단, 경우의 수를 각각 찾고 난 후에는 다시 제자리로 돌려 두어야한다.
마지막으로, 이 모든 경우를 찾기 전 경우의 수를 미리 구해둔다.

코드

import java.io.*;

public class Main {
    static int N;
    static char[][] candy;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        // 캔디 위치 입력받음
        candy = new char[N][N];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                candy[i][j] = str.charAt(j);
            }
        }

        int max = 0;

        // 바꾸기전 카운트
        for (int i = 0; i < N; i++) {
            max = Math.max(max, countColumn(i));
        }
        for (int i = 0; i < N; i++) {
            max = Math.max(max, countRow(i));
        }


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (j + 1 < N) { // 행 : 좌, 우 swap
                    swap(i, j, i, j + 1); // 오른쪽이랑 swap
                    max = Math.max(max, countColumn(i)); // 행 영향
                    max = Math.max(max, countRow(j)); // 열 영향 1
                    max = Math.max(max, countRow(j + 1)); // 열 영향 2
                    swap(i, j, i, j + 1); // 복귀
                }
                if (i + 1 < N) { 
                /* 열 : 상, 하 swap (항상 다음 원소랑 비교하므로 바꿀 다음 원소가 범위 내에있는지
                 체크하여야한다.) */
                    swap(i, j, i + 1, j); // 아래쪽이랑 swap
                    max = Math.max(max, countColumn(i)); // 영향 받는 가로 카운트 1
                    max = Math.max(max, countColumn(i + 1)); // 영향 받는 가로 카운트 2
                    max = Math.max(max, countRow(j)); // 영향 받는 세로 카운트
                    swap(i, j, i + 1, j); // 복귀
                }
            }
        }

        bw.write(String.valueOf(max)); // 모든 경우에 대해서 최대값 출력

        bw.flush();
        br.close();
        bw.close();
    }

	// 가로로 카운트 하는 경우
    private static int countColumn(int x) {
        char color = candy[x][0]; // 처음 색깔 저장

        int max = 0;
        int count = 1; // 갱신되면 첫번째 원소는 카운트 안하므로 1로 해둔다.
        for (int column = 1; column < N; column++) {
            if (color != candy[x][column]) { // 색깔을 다른거 만나면 교체후 그 색깔로 계속 카운트
                color = candy[x][column];
                max = Math.max(max,count);
                count = 1;
                continue;
            }
            count++; // 같으면 계속 카운트
        }

        return Math.max(count, max);
    }

	// 세로로 카운트 하는 경우
    private static int countRow(int y) {
        char color = candy[0][y];

        int count = 1;
        int max = 0;
        // 세로로 확인
        for (int row = 1; row < N; row++) {
            if (color != candy[row][y]) {
            // 색깔이 다른 경우 : 갱신한다. 카운트도 갱신
                color = candy[row][y];
                max = Math.max(count, max);
                count = 1;
                continue;
            }
            count++;
        }

        max = Math.max(count, max);

        return max;
    }

	// swap 함수, 차라리 바꾸고 돌려놓는 경우가 경우의 수를 찾기 편하다.
    private static void swap(int x, int y, int newX, int newY) {
        char temp = candy[x][y];
        candy[x][y] = candy[newX][newY];
        candy[newX][newY] = temp;
    }


}

결론

되게 헤맨 문제, 모든 경우의 수를 나눠서 풀려고 하면 오히려 꼬이는 문제.
사탕게임, 숫자야구 대표적 브루트포스 구현문제 같다.
출처 : https://yeeybook.tistory.com/144