백준 - 사탕 게임

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

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

 

[문제 설명]

 

[접근 방법]

 

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

class Main {
    static char[][] board;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new char[N][N];
        for (int i = 0; i < N; i++) { board[i] = br.readLine().toCharArray(); }
        int answer = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N-1; j++) {
                // 가로 인접한 게 다른 경우
                if (board[i][j] != board[i][j+1]) {
                    // 인접한 두개 바꾸기
                    swap(i,j,i,j+1);

                    // 같은 글자가 한 줄에 몇개인지 세기
                    for (int k = 0; k < N; k++) {
                        answer = Math.max(answer,count(true, k));
                        answer = Math.max(answer,count(false, k));
                    }

                    // 바꾼 두개 원위치
                    swap(i,j,i,j+1);
                }
                // 세로 인접한 게 다른 경우
                if (board[j][i] != board[j+1][i]) {
                    // 인접한 두개 바꾸기
                    swap(j,i,j+1,i);

                    // 같은 글자가 한 줄에 몇개인지 세기
                    for (int k = 0; k < N; k++) {
                        answer = Math.max(answer,count(true, k));
                        answer = Math.max(answer,count(false, k));
                    }

                    // 바꾼 두개 원위치
                    swap(j,i,j+1,i);
                }

                // answer이 N이면 가질 수 있는 최대값이므로 리턴
                if (answer == N) {
                    System.out.println(N);
                    return;
                }
            }
        }
        System.out.println(answer);
    }

    private static void swap(int x, int y, int x2, int y2) {
        char temp = board[x][y];
        board[x][y] = board[x2][y2];
        board[x2][y2] = temp;
    }

    private static int count(boolean isHorizontialWay, int pivotA) {
        // 수평으로 두개 세기
        char pivotChar;
        int tempNumOfSameChar = 0;
        int numOfSameChar = 1;
        if (isHorizontialWay) {
            pivotChar = board[pivotA][0];
            for (int i = 1; i < N; i++) {
                if (board[pivotA][i] == pivotChar) numOfSameChar++;
                else {
                    pivotChar = board[pivotA][i];
                    tempNumOfSameChar = Math.max(tempNumOfSameChar, numOfSameChar);
                    numOfSameChar = 1;
                }
            }
            tempNumOfSameChar = Math.max(tempNumOfSameChar, numOfSameChar);
        } else {
            // 수직으로 세기
            pivotChar = board[0][pivotA];
            for (int i = 1; i < N; i++) {
                if (board[i][pivotA] == pivotChar) numOfSameChar++;
                else {
                    pivotChar = board[i][pivotA];
                    tempNumOfSameChar = Math.max(tempNumOfSameChar, numOfSameChar);
                    numOfSameChar = 1;
                }
            }
            tempNumOfSameChar = Math.max(tempNumOfSameChar, numOfSameChar);
        }

        return tempNumOfSameChar;
    }
}