[백준] 3085번 : 사탕 게임 - JAVA [자바]

https://www.acmicpc.net/problem/3085

브루트포스 알고리즘 문제이다.

인접한 캔디의 색이 다를때 바꾸는 경우는 두 가지가 있다.

1. 내 오른쪽 캔디와의 색깔이 다를때 바꾸는 경우
2. 내 아래 캔디와의 색깔이 다를때 바꾸는 경우

각 캔디마다 이 두가지 경우를 생각해주면 바꿀 수 있는 모든 경우의 수는 처리가 된다.

푸는 순서

1. 현재 i 번째 줄에서 j 번째 캔디일 때 내 오른쪽과 아래쪽을 보고 다른 색의 캔디이면 캔디를 바꿔준다.
2. 바뀐 상황에서 먹을 수 있는 최대의 캔디 갯수를 구한다.

참고: 배열의 범위를 잘 생각해서 만약에 마지막 줄일때는 아래쪽을 볼 필요가 없고 제일 오른쪽 줄일때는 오른쪽을 볼 필요가 없다.

public class bj3085 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        char[][] candy = new char[N][N];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            char[] charArray = line.toCharArray();
            for (int j = 0; j < N; j++) {
                candy[i][j] = charArray[j];
            }
        }

        int answer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
            	// 현재 제일 오른쪽에 있는 경우 오른쪽을 볼 필요가 없다
                if (j != N - 1) {
                	// 오른쪽에 다른 색의 캔디일 때
                    if (candy[i][j] != candy[i][j + 1]) {
                        // 캔디 체인지
                        changeCandyRight(j, candy[i]);
                        // 그때 먹을 수 있는 사탕의 최대 개수
                        answer = countCandy(N, candy, answer);
                        // 원상 복구
                        changeCandyRight(j, candy[i]);
                    }
                }
                // 현재 제일 아래쪽일 경우 아래쪽을 볼 필요가 없다
                if (i != N - 1) {
                	// 아래쪽에 다른 색의 캔디일 때
                    if (candy[i][j] != candy[i + 1][j]) {
                        // 캔디 체인지
                        changeCandyBottom(candy[i], j, j, candy[i + 1]);
                        // 그때 먹을 수 있는 사탕의 최대 개수
                        answer = countCandy(N, candy, answer);
                        // 원상 복구
                        changeCandyBottom(candy[i], j, j, candy[i + 1]);
                    }
                }
            }
        }

        bw.write(answer + "\n");

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

	// 현재 바뀐 캔디 배열에서 먹을 수 있는 캔디의 최대 갯수를 구한다.
    private static int countCandy(int N, char[][] candy, int answer) { 
    	// 배열에서 x 번째 줄 y 번째 캔디일 때
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                // 현재 캔디를 먹으면서 시작하기 때문에 count = 1
                int count = 1;
                // 오른쪽의 캔디를 본다.
                for (int q = y + 1; q < N; q++) {
                	// 같은 색의 캔디이다.
                    if (candy[x][y] == candy[x][q]) {
                    	// 먹는다
                        count++;
                    } else break; // 다른 색의 캔디다 
                }
                // 현재 최대 갯수 보다 더 크면 업데이트
                if (count > answer) answer = count;
                // 다시 아래로 먹는 과정을 본다
                // 현재 캔디를 먹기 때문에 count = 1
                count = 1;
                // 아래족 캔디를 본다
                for (int q = x + 1; q < N; q++) {
                	// 같은 색의 캔디다
                    if (candy[x][y] == candy[q][y]) {
                    	// 먹는다
                        count++;
                    } else break; // 다른 색의 캔디다
                }
                // 현재 최대 갯수 보다 더 크면 업데이트
                if (count > answer) answer = count;
            }
        }
        
        return answer;
    }
	// 아래쪽의 캔디와 바꾼다
    private static void changeCandyBottom(char[] candy, int j, int j1, char[] candy1) {
        char temp = candy[j];
        candy[j] = candy1[j1];
        candy1[j1] = temp;
    }
	// 오른쪽의 캔디와 바꾼다
    private static void changeCandyRight(int j, char[] candy) {
        changeCandyBottom(candy, j, j + 1, candy);
    }
}