[백준 코딩테스트 문제] 3085번 사탕 게임.Java

 

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

 

문제

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

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

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

입력

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

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

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

출력

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

---

 

문제 이해:

1. N x N 크기의 보드가 주어집니다 (3 ≤ N ≤ 50).
2. 보드의 각 칸에는 사탕이 하나씩 들어있고, 사탕의 색상은 빨간색(C), 파란색(P), 초록색(Z), 노란색(Y) 중 하나입니다.
3. 인접한 두 사탕의 위치를 한 번 바꿀 수 있습니다.
4. 같은 색으로 이루어진 가장 긴 연속 부분(행 또는 열)의 사탕을 모두 먹을 수 있습니다.
5. 먹을 수 있는 사탕의 최대 개수를 구해야 합니다.

해결 방법:

1. 보드 입력 받기:
   • Scanner를 사용하여 N을 입력받고, N x N 크기의 2차원 char 배열을 생성합니다.
   • N개의 줄에 걸쳐 각 줄의 사탕 색상을 입력받아 배열에 저장합니다.
2. 모든 가능한 교환 시도:
   • 이중 for 루프를 사용하여 보드의 모든 위치를 순회합니다.
   • 각 위치에서 오른쪽 사탕과 아래쪽 사탕을 교환해봅니다.
   • 교환 후 최대 사탕 개수를 계산하고, 원래 상태로 되돌립니다.
3. 최대 사탕 개수 계산 (countMaxCandies 메소드):
   • 모든 행과 열을 검사하여 연속된 같은 색상의 사탕 수를 세어 최대값을 갱신합니다.
   • 행 검사: 각 행을 왼쪽에서 오른쪽으로 순회하며 연속된 같은 색상의 사탕 수를 셉니다.
   • 열 검사: 각 열을 위에서 아래로 순회하며 연속된 같은 색상의 사탕 수를 셉니다.
4. 결과 출력:
   • 모든 가능한 교환을 시도한 후 찾은 최대 사탕 개수를 출력합니다.

주요 메소드 설명:

1. main 메소드:
   • 프로그램의 진입점입니다.
   • 입력을 받고 solve 메소드를 호출하여 결과를 출력합니다.
2. solve 메소드:
   • 모든 가능한 교환을 시도합니다.
   • 각 교환마다 countMaxCandies를 호출하여 최대값을 갱신합니다.
3. swap 메소드:
   • 두 위치의 사탕을 교환합니다.
4. countMaxCandies 메소드:
   • 현재 보드 상태에서 가장 긴 연속된 같은 색상의 사탕 수를 계산합니다.

시간 복잡도:

• 전체 알고리즘의 시간 복잡도는 O(N^3)입니다.
• N x N 보드의 모든 위치를 순회하며 (O(N^2)), 각 위치에서 교환 후 최대 개수를 계산합니다 (O(N)).
• N이 최대 50이므로, 이 방법으로 충분히 해결할 수 있습니다.

이 알고리즘은 '브루트 포스' 방식으로, 모든 가능한 경우를 다 시도해보고 그 중 최대값을 찾는 방법입니다. 문제의 조건(N ≤ 50)에서 이 방법이 충분히 효율적입니다.

 

 

import java.util.Scanner;

public class Main {
    static int N;
    static char[][] board;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        scanner.nextLine(); // 버퍼 비우기

        board = new char[N][N];
        for (int i = 0; i < N; i++) {
            String line = scanner.nextLine();
            board[i] = line.toCharArray();
        }

        System.out.println(solve());
        scanner.close();
    }

    static int solve() {
        int maxCandies = 0;

        // 모든 인접한 두 사탕의 위치를 바꿔보며 최대값 찾기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 오른쪽과 교환
                if (j + 1 < N) {
                    swap(i, j, i, j + 1);
                    maxCandies = Math.max(maxCandies, countMaxCandies());
                    swap(i, j, i, j + 1); // 원상복구
                }

                // 아래와 교환
                if (i + 1 < N) {
                    swap(i, j, i + 1, j);
                    maxCandies = Math.max(maxCandies, countMaxCandies());
                    swap(i, j, i + 1, j); // 원상복구
                }
            }
        }

        return maxCandies;
    }

    static void swap(int i1, int j1, int i2, int j2) {
        char temp = board[i1][j1];
        board[i1][j1] = board[i2][j2];
        board[i2][j2] = temp;
    }

    static int countMaxCandies() {
        int maxCount = 0;

        // 행에서 최대 연속 개수 확인
        for (int i = 0; i < N; i++) {
            int count = 1;
            for (int j = 1; j < N; j++) {
                if (board[i][j] == board[i][j - 1]) {
                    count++;
                } else {
                    maxCount = Math.max(maxCount, count);
                    count = 1;
                }
            }
            maxCount = Math.max(maxCount, count);
        }

        // 열에서 최대 연속 개수 확인
        for (int j = 0; j < N; j++) {
            int count = 1;
            for (int i = 1; i < N; i++) {
                if (board[i][j] == board[i - 1][j]) {
                    count++;
                } else {
                    maxCount = Math.max(maxCount, count);
                    count = 1;
                }
            }
            maxCount = Math.max(maxCount, count);
        }

        return maxCount;
    }
}