백준 3085번 - 사탕게임 / Java

문제

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

3085번: 사탕 게임

모든 경우의 수를 탐색해서 답을 구하는 문제. 브루트포스이다 

접하는 두칸을 변경하는데 걸리는 시간N^2 배열을 검사하는데 걸리는시간 N^2

따라서 모든경우의 수를 탐색할 경우 걸리는 시간은 O(N^4)이다

N의 최댓값은 50이므로 약 6,250,000의 경우의수가 나온다.

많지 않은 경우이므로 브루트포스로 풀 수 있다.

 

알고리즘

1. 인접한 칸의 사탕이 다를경우 서로 바꿔준다

2. 먹을 수 있는 사탕의 개수를 계산한다

3. 최댓값을 출력한다

소스코드

/*
 * BOJ3085
 * 2020.01.20
 * Hyeonseong
 */
import java.util.*;
public class BOJ3085
{
    public static void main(String[] args) 
    {
        Solution s = new Solution();
    }
}
class Solution{
    char[][] candy;
    int max;
    public Solution() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        max = 0;
        candy = new char[n][n];
        for(int i=0;i<n;i++) {
            candy[i] = scan.next().toCharArray();
        }
        char temp=' ';
        
        for(int i=0;i<n;i++) { // 가로 확인
            for(int j=0;j<n-1;j++) {
                if(candy[i][j] != candy[i][j+1]) {
                    temp= candy[i][j];
                    candy[i][j] = candy[i][j+1];
                    candy[i][j+1] = temp;
                    check();
                    temp = candy[i][j];
                    candy[i][j] = candy[i][j+1];
                    candy[i][j+1] = temp;
                }
            }
        }
        for(int i=0;i<n;i++) { // 세로확인
            for(int j=0;j<n-1;j++) {
                if(candy[j][i]!=candy[j+1][i]) {
                    temp = candy[j][i];
                    candy[j][i] = candy[j+1][i];
                    candy[j+1][i] = temp;    
                    check();
                    temp = candy[j][i];
                    candy[j][i] = candy[j+1][i];
                    candy[j+1][i] = temp;    
                }
            }
        }
        System.out.println(max);
    }
    public void check(){
        int num = 1;
        for(int i=0;i<candy.length;i++) { // 가로체크
            num = 1;
            for(int j=0;j<candy[i].length-1;j++) {
                if(candy[i][j]==candy[i][j+1]) {
                    num++;
                    if(max < num) {
                        max = num;
                    }
                }
                else {
                    num = 1;
                }
            }
        }
        for(int i=0;i<candy.length;i++) { // 세로체크
            num = 1;
            for(int j=0;j<candy[i].length-1;j++) {
                if(candy[j][i]==candy[j+1][i]) {
                    num++;
                    if(max < num) {
                        max = num;
                    }
                }
                else {
                    num = 1;
                }
            }
        }
    }
}