3085 사탕 게임

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	24568	8004	5555	31.810%

문제

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

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

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

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력 1

3
CCP
CCP
PPC

예제 출력 1

3

예제 입력 2

4
PPPP
CYZY
CCPY
PPCC

예제 출력 2

4

예제 입력 3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 3

4

코드

import java.io.*;

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

        int n = Integer.parseInt(br.readLine());
        String[][] arr = new String[n][n];
        for (int i = 0; i < n; i++) {
            arr[i] = br.readLine().split("");
        }

        String tmp;
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                tmp = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = tmp;
                max = (max > count_candy(n, arr)) ? max : count_candy(n, arr);
                tmp = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                tmp = arr[j][i];
                arr[j][i] = arr[j + 1][i];
                arr[j + 1][i] = tmp;
                max = (max > count_candy(n, arr)) ? max : count_candy(n, arr);
                tmp = arr[j][i];
                arr[j][i] = arr[j + 1][i];
                arr[j + 1][i] = tmp;
            }
        }
        bw.write(Integer.toString(max));
        bw.flush();
    }

    public static int count_candy(int n, String[][] arr) {
        int count;
        int ans = 0;
        String ch;

        for (int i = 0; i < n; i++) {
            count = 1;
            ch = arr[i][0];
            for (int j = 1; j < n; j++) {
                if (arr[i][j].equals(ch))
                    count++;
                else
                    count = 1;
                ch = arr[i][j];
                ans = (ans > count) ? ans : count;
            }
        }

        for (int i = 0; i < n; i++) {
            count = 1;
            ch = arr[0][i];
            for (int j = 1; j < n; j++) {
                if (arr[j][i].equals(ch))
                    count++;
                else
                    count = 1;
                ch = arr[j][i];
                ans = (ans > count) ? ans : count;
            }
        }

        return ans;
    }
}

코드 내용

행과 열을 각각 바꿔보면서 전체적으로 연속된 candy의 개수를 세는 알고리즘을 선택했다.

처음에는 바뀐 열과 행만 검사를 했는데 코드가 점점 꼬이기도 했고, 매번 완전 탐색을 하더라도 O(n^2) = O(2500)으로 2초가 넘지 않아서 간단하게 매번 완전 탐색을 하는 것으로 선택했다.

연속적인 캔디의 개수를 셀 때는 캔디의 색을 ch에 저장하였고, 매번 ch를 바꿔주는 것으로 계산했다. 만약 ch와 현재 참조하고 있는 곳의 캔디의 색이 같다면 count를 1씩 증가시켜주었고, 아니라면 count를 1로 초기화해서 다시 연속적인 candy의 개수를 셀 수 있도록 했다.

swap함수를 따로 작성했었는데 call by value가 되어서 candy 배열이 변경이 되지 않아 그냥 main함수에서 여러번 작성했는데 이 점이 조금 아쉽다.