백준 3085번 사탕게임 :: 마이구미

이 글은 백준 알고리즘 3085번 "사탕 게임" 을 풀이한다.

방법은 브루트 포스(노가다)를 통해 해결한다.

문제 링크 - https://www.acmicpc.net/problem/3085

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

문제는 인접한 두 칸을 고른 후, 고른 칸을 서로 교환(swap)한 후 행 또는 열에서 같은 색의 수가 최대일 경우를 찾는다.

N의 크기도 최대 50인 점과 단순히 생각해도 모든 경우를 확인하면 된다.

주의할 점은 다음과 같다.

1. 인접한 두 칸은 가로 또는 세로이다. 대각선은 인접하다는 의미가 아니다.
2. 두 칸을 스왑한 후, 다음 스왑을 위해 사탕을 원본 상태로 돌려놓아야한다.

위 2가지만 잘 고려한다면, 문제를 쉽게 해결할 수 있다.

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/Brute-Force/3085.java

static int ans;
static char[][] map;
static int n;
 
private void solve() {
    n = sc.nextInt();
    map = new char[n][n];
 
    for (int i = 0; i < n; i++) {
        map[i] = sc.readLine().toCharArray();
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            char temp = map[i][j];
            map[i][j] = map[i][j + 1];
            map[i][j + 1] = temp;
            check();
            temp = map[i][j + 1];
            map[i][j + 1] = map[i][j];
            map[i][j] = temp;
 
            temp = map[j][i];
            map[j][i] = map[j + 1][i];
            map[j + 1][i] = temp;
            check();
            temp = map[j + 1][i];
            map[j + 1][i] = map[j][i];
            map[j][i] = temp;
        }
    }
    System.out.println(ans);
}
 
public static void check() {
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        for (int j = 1; j < n; j++) {
            if (map[i][j] == map[i][j - 1]) {
                ++cnt;
            } else {
                ans = max(ans, cnt);
                cnt = 1;
            }
        }
        ans = max(ans, cnt);
    }
 
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        for (int j = 1; j < n; j++) {
            if (map[j][i] == map[j - 1][i]) {
                ++cnt;
            } else {
                ans = max(ans, cnt);
                cnt = 1;
            }
        }
        ans = max(ans, cnt);
    }
}
 
public static int max(int x, int y) {
    return x > y ? x : y;
}