[Java] 3085 사탕 게임

문제

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

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

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

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

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

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

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

 

요약하자면 인접한 다른 캔디 위치를 교환했을 때 가장 긴 한 줄이 얼마냐라는 것이다.

별다른 자료구조를 활용하는 것이 아닌 일일이 확인할 수 밖에 없는 브루트 포스 문제이다.

확인을 위해 첫 번째 자리 부터 오른쪽, 아랫쪽을 한 번씩 교환해보면서 확인하는 방식을 차용한다.

 

위나 왼쪽을 확인할 필요는 없다. 오른쪽과 아랫쪽을 교환했을 때 이미 확인된 위치이기 때문이다.

XYY                             YXY
YYX 라고 가정했을 때 YYX 로 바꿨다고 해보자 (첫 행의 첫 열 X를 기준으로 오른쪽 Y와 교환)

이후 첫 행의 두 열 Y를 왼쪽의 X와 교환해봐야 이미 비교했었기 때문에 의미가 없다는 의미)

문제 풀이

1. 입력받은 숫자 크기 만큼의 이차원 Char 배열을 생성한다.

2. 한 줄 한 줄 입력받은 문자열을 한 글자씩 배열에 삽입한다.

3. [0][0] 자리의 글자부터 오른쪽 글자와 교환해간다.

4. 이때 한 번 교환할 때마다 가장 길게 이어지는 행이나 열이 얼마인지 확인하고 기록한다.

5. 해당 작업이 종료된 뒤 교환한 글자들을 기존 자리로 되돌리고 다음 열의 글자부터 다시 3을 반복한다.

6. 오른쪽 방향으로의 검사가 끝난 뒤 같은 방식으로 아랫쪽 글자와도 비교해간다.

7. 마지막으로 기록된 최대 길이를 출력한다.

자바 코드

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

public class Main {
    private static int max = 1;
    private static int size;
    private static char[][] board;

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

        size = Integer.parseInt(br.readLine());
        board = new char[size][size];

        // 보드에 캔디 삽입
        for(int i = 0; i < size; i++){
            String candyLine = br.readLine();

            for(int j = 0; j < size; j++){
                board[i][j] = candyLine.charAt(j);
            }
        }
        
        // 행 기준 오른쪽과 변경
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size -1; j++){
                // 오른쪽 열과 변경
                candySwap(i, j, i, j + 1);
                
                // 최대 연결 캔디 검사
                searchMaxCandy();

                // 변경한 열 다시 되돌리기
                candySwap(i , j + 1, i, j);
            }
        }
        // 행 기준 아래쪽과 변경
        for(int i = 0; i < size - 1; i++){
            for(int j = 0; j < size; j++){
                // 아랫쪽 행과 변경
                candySwap(i, j, i + 1, j);

                // 최대 연결 캔디 검사
                searchMaxCandy();

                // 변경한 행 다시 되돌리기
                candySwap(i + 1 , j, i, j);
            }
        }

        System.out.println(max);
    }

    private static void candySwap(int beforeX, int beforeY, int afterX, int afterY){
        char temp = board[beforeX][beforeY];
        board[beforeX][beforeY] = board[afterX][afterY];
        board[afterX][afterY] = temp;
    }

    private static void searchMaxCandy(){
        for(int i = 0; i < size; i++){
            int count = 1;

            for(int j = 0; j < size - 1; j++){
                if(board[i][j] == board[i][j + 1])
                    max = Math.max(++count, max);
                else
                    count = 1;
            }
        }

        for(int i = 0; i < size; i++){
            int count = 1;

            for(int j = 0; j < size - 1; j++){
                if(board[j][i] == board[j + 1][i])
                    max = Math.max(++count, max);
                else
                    count = 1;
            }
        }
    }
}