[백준 *Java] - 사탕게임 (3085)

 

사탕 게임 문제보기

3085번: 사탕 게임

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N x N 크기에 사탕을 채워 놓는다.
사탕의 색은 모두 같지 않을 수도 있다.
상근이는 사탕의 색이 다른 인접한 두 칸을 고른다.
그 다음 고른 칸에 들어 있는 사탕을 서로 교환한다.
이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 

👇  접근방식 (내생각 정리)

완전탐색 문제로, 모든 경우를 다 따져야하는 문제입니다.

 좌우(가로), 상하(세로)로 인접한 두 칸을 교환하는 작업을 한 뒤에 같은 색으로 이루어져 있는 걸 count 해주는 작업입니다.

N <= 50 이기 때문에, 브루트포스로 모든 경우의 수를 반복문을 통해서 거쳐가면서 확인해주면 됩니다.

 

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

public class Main {
    static char[][] arr;

    // 갯수를 카운트하는 메서드
    static public int check(char[][] arr, int rowSt, int rowEnd, int colSt, int colEnd) {
        int result = Integer.MIN_VALUE;

        for (int i = rowSt; i <= rowEnd; i++) {
            int cnt = 1; // 1부터 시작 갯수 1초기화
            for (int j = 1; j < arr.length; j++) {
                if (arr[i][j] == arr[i][j - 1]) {
                    cnt += 1;
                } else 
                    cnt = 1; // 리셋
                
                if (cnt > result) result = cnt;
            }
        }

        for (int i = colSt; i <= colEnd; i++) {
            int cnt = 1; // 1부터 시작 갯수 1초기화
            for (int j = 1; j < arr.length; j++) {
                if (arr[j][i] == arr[j - 1][i]) {
                    cnt += 1;
                } else 
                    cnt = 1; // 리셋
                
                if (cnt > result) result = cnt;
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new char[N][N];

        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine().toCharArray();
        }


        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 열
                if (N > i + 1) {
                    char temp = arr[i][j];
                    arr[i][j] = arr[i + 1][j];
                    arr[i + 1][j] = temp;

                    int tmp = check(arr, i, i + 1, j, j);
                    if (max < tmp) max = tmp; // 최댓값 갱신

                    temp = arr[i][j];
                    arr[i][j] = arr[i + 1][j];
                    arr[i + 1][j] = temp;
                }

                // 행
                if (N > j + 1) {
                    // 교환작업
                    char temp = arr[i][j];
                    arr[i][j] = arr[i][j + 1];
                    arr[i][j + 1] = temp;
                    // 갯수 카운트를 합니다 !
                    int tmp = check(arr, i, i, j, j + 1);
                    if (max < tmp) max = tmp; // 최대값으로 갱신

                    // 교환작업한 걸 원상복구
                    temp = arr[i][j];
                    arr[i][j] = arr[i][j + 1];
                    arr[i][j + 1] = temp;
                }
            }
        }
        System.out.println(max);
    }
}