백준 3085번 문제: 사탕 게임 (Java)

이번 포스트에서는 백준 3085번 문제를 해결하는 방법에 대해 설명하겠습니다. 문제는 NxN 크기의 사탕판에서 인접한 두 사탕을 교환하여 같은 색의 사탕이 연속으로 가장 많이 이어지는 부분의 사탕 개수를 구하는 것입니다. 이를 위해 다음과 같은 방법으로 접근하였습니다.

문제 해결 흐름

1. 입력 받기: 표의 크기와 각 셀의 사탕 색깔을 입력받습니다.
2. 최대 연속 사탕 개수 찾기: 주어진 표에서 행과 열을 검사하여 같은 색의 사탕이 연속으로 이어진 최대 개수를 찾습니다.
3. 사탕 교환 및 검사: 인접한 두 사탕을 교환하고 최대 연속 사탕 개수를 다시 계산합니다. 이후 원래 상태로 복구합니다.
4. 결과 출력: 모든 교환을 시도한 후 최대 연속 사탕 개수를 출력합니다.

코드

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

public class P3085 {
    // 주어진 배열에서 가장 긴 연속 부분을 찾는 함수
    private static int findMax(char[][] arr, int n) {
        int max = 0;

        // 가로 검사
        for (int i = 0; i < n; i++) {
            int tempCount = 1;
            for (int j = 1; j < n; j++) {
                if (arr[i][j] == arr[i][j-1]) {
                    tempCount++;
                } else {
                    max = Math.max(max, tempCount);
                    tempCount = 1;
                }
            }
            max = Math.max(max, tempCount);
        }

        // 세로 검사
        for (int j = 0; j < n; j++) {
            int tempCount = 1;
            for (int i = 1; i < n; i++) {
                if (arr[i][j] == arr[i-1][j]) {
                    tempCount++;
                } else {
                    max = Math.max(max, tempCount);
                    tempCount = 1;
                }
            }
            max = Math.max(max, tempCount);
        }

        return max;
    }

    // 메인 함수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[][] table = new char[n][n];

        // 입력 받기
        for (int i = 0; i < n; i++) {
            String row = br.readLine();
            for (int j = 0; j < n; j++) {
                table[i][j] = row.charAt(j);
            }
        }

        int countMax = 0;

        // 사탕 교환 및 최대 연속 사탕 개수 계산
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 가로로 교환
                if (j < n - 1 && table[i][j] != table[i][j + 1]) {
                    swap(table, i, j, i, j + 1);
                    countMax = Math.max(countMax, findMax(table, n));
                    swap(table, i, j, i, j + 1); // 원상복구
                }

                // 세로로 교환
                if (i < n - 1 && table[i][j] != table[i + 1][j]) {
                    swap(table, i, j, i + 1, j);
                    countMax = Math.max(countMax, findMax(table, n));
                    swap(table, i, j, i + 1, j); // 원상복구
                }
            }
        }

        // 결과 출력
        System.out.println(countMax);
    }

    // 배열의 두 요소를 교환하는 함수
    private static void swap(char[][] arr, int i1, int j1, int i2, int j2) {
        char temp = arr[i1][j1];
        arr[i1][j1] = arr[i2][j2];
        arr[i2][j2] = temp;
    }
}

코드 설명

1. 입력 받기

BufferedReader를 사용하여 입력을 받고, 이를 table 배열에 저장합니다.

2. 최대 연속 사탕 개수 찾기

findMax 함수는 주어진 배열에서 가장 긴 연속된 사탕의 개수를 계산합니다. 가로와 세로를 각각 검사하여 최대 값을 갱신합니다.

3. 사탕 교환 및 검사

이중 for 루프를 사용하여 각 위치에서 가로와 세로로 인접한 사탕을 교환합니다. 교환 후 findMax 함수를 호출하여 최대 연속 사탕 개수를 계산하고, 다시 원상복구합니다.

4. 결과 출력

모든 교환을 시도한 후 최대 연속 사탕 개수를 출력합니다.

결론

이 코드의 핵심은 인접한 사탕을 교환하고 최대 연속 사탕 개수를 계산하는 것입니다. 모든 가능한 교환을 시도하여 최종 결과를 도출합니다. 이 방법으로 백준 3085번 문제를 성공적으로 해결할 수 있습니다.