[JAVA] 백준 3085번_ 사탕 게임

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

3085번: 사탕 게임

- 가장 연속된 부분이 긴 부분을 찾아서 탐색해보기 -> 너무 비효율적임

- N 크기가 크지 않으므로 완전 탐색도 괜찮을 것 같음 (연속된 알파벳이 다른 경우만 탐색하므로)

- 오른쪽, 아래와 교환 후 각 알파벳에 대해 같은 수 탐색

• 오른쪽 교환인 경우 체크 : row 1개, col 2개
• 아래 교환시 체크 : row 2개, col 1개

- 한 줄 내 최대 연속 개수 체크

---

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

public class Main_3085 {
    static int[][] map;
    static int N, maxEat = 0;
    static String str;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            str = br.readLine();
            for (int j = 0; j < N; j++) {
                switch (str.charAt(j)) {
                    case 'C':
                        map[i][j] = 0; break;
                    case 'P':
                        map[i][j] = 1; break;
                    case 'Z':
                        map[i][j] = 2; break;
                    case 'Y':
                        map[i][j] = 3; break;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N-1; j++) {
                if(j + 1 < N){ //오른쪽 탐색
                    swap(i, j, i, j+1);
                    search(i, true);
                    search(j, false);
                    search(j+1, false);
                    swap(i, j, i, j+1);
                }
                if(i + 1 < N) {//아래 교환 후 탐색
                    swap(i, j, i+1, j);
                    search(i, true);
                    search(i+1, true);
                    search(j, false);
                    swap(i, j, i+1, j);
                }
            }
        }
        System.out.println(maxEat);
    }

    private static void search(int f, boolean isRow) {
        int[] tmpMax = {0, 0, 0, 0};
        int color, cnt = 1;
        if(isRow){
            //i == row
            color = map[f][0];
            for (int j = 1; j < N; j++) {
                if(color != map[f][j]){
                    tmpMax[color] = Math.max(tmpMax[color], cnt);
                    color = map[f][j];
                    cnt = 1;
                }else{
                    cnt++;
                }
            }
            tmpMax[color] = Math.max(tmpMax[color], cnt);
        }else{
            color = map[0][f];
            for (int j = 1; j < N; j++) {
                if(color != map[j][f]){
                    tmpMax[color] = Math.max(tmpMax[color], cnt);
                    color = map[j][f];
                    cnt = 1;
                }else{
                    cnt++;
                }
            }
            tmpMax[color] = Math.max(tmpMax[color], cnt);
        }
        maxEat = Math.max(Arrays.stream(tmpMax).max().getAsInt(), maxEat);
    }

    private static void swap(int r1, int c1, int r2, int c2) {
        int tmp = map[r1][c1];
        map[r1][c1] = map[r2][c2];
        map[r2][c2] = tmp;
    }

}