[Algorithm] 백준 3085번_사탕_게임(Java)

🔗 3085번 사탕 게임

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

 

문제

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

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

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

 

입력

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

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

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

 

출력

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

 

🧠 접근 방법

이 문제는 보드 위의 사탕 색깔을 바꿔가며 같은 색으로 이어진 최대 사탕 개수를 찾는 문제이다.
단, 사탕을 바꿀 수 있는 기회는 딱 한 번이며, 인접한 칸만 서로 교환 가능하다.

1.    모든 칸에 대해 좌우, 상하 인접한 칸과 교환해보기
2.    교환 후, 현재 보드 상태에서 가장 긴 연속된 사탕의 개수를 확인
3.    다시 원상복구
4.    이 중 최댓값을 갱신하며 정답을 구한다

즉, 완전 탐색(Brute Force)을 하되, 하나씩 바꿔보며 최대값을 계속 추적하는 방식이다.

 

✏️ 풀이 과정

1. 보드 입력 받기
• 보드는 char[N][N] 2차원 배열로 선언
• BufferedReader와 toCharArray()를 통해 빠르게 입력 처리

board[i] = br.readLine().toCharArray();

 

2. 모든 칸에 대해 상하 / 좌우 교환 시도
범위 조건(j < N-1, i < N-1)을 체크해서 배열 인덱스 에러를 방지해준다.
교환은 swap() 함수로 분리 구현

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        // 좌우 교환
        if (j < N - 1) {
            swap(i, j, i, j + 1);
            maxCandies = Math.max(maxCandies, countCandies());
            swap(i, j, i, j + 1); // 원복
        }

        // 상하 교환
        if (i < N - 1) {
            swap(i, j, i + 1, j);
            maxCandies = Math.max(maxCandies, countCandies());
            swap(i, j, i + 1, j); // 원복
        }
    }
}

 

3. 사탕 개수 세기 (countCandies)

public static int countCandies() {
    for (int i = 0; i < N; i++) {
        int rowCnt = 1, colCnt = 1;
        for (int j = 1; j < N; j++) {
            // 가로 방향 검사
            if (board[i][j] == board[i][j - 1]) rowCnt++;
            else {
                maxLen = Math.max(maxLen, rowCnt);
                rowCnt = 1;
            }

            // 세로 방향 검사
            if (board[j][i] == board[j - 1][i]) colCnt++;
            else {
                maxLen = Math.max(maxLen, colCnt);
                colCnt = 1;
            }
        }
        // 마지막 줄에 대해 누락 방지
        maxLen = Math.max(maxLen, rowCnt);
        maxLen = Math.max(maxLen, colCnt);
    }
    return maxLen;
}

 

이렇게 하면 교환된 상태에서 가장 긴 연속 사탕 개수를 바로 구할 수 있다

 

💻 전체 코드

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        board = new char[N][N];

        int maxCandies = Integer.MIN_VALUE;

        for(int i = 0; i < N; i++){
            board[i] = br.readLine().toCharArray();
        }

        for(int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 좌우
                if( j < N - 1) {
                    swap(i, j, i, j + 1);
                    maxCandies = Math.max(maxCandies, countCandies());
                    swap(i, j, i, j + 1);
                }

                // 상하
                if(i < N - 1) {
                    swap(i, j, i + 1, j);
                    maxCandies = Math.max(maxCandies, countCandies());
                    swap(i, j, i + 1, j);
                }

            }
        }
        System.out.println(maxCandies);
    }
    public static void swap(int x, int y, int nx, int ny) {
        char temp = board[x][y];
        board[x][y] = board[nx][ny];
        board[nx][ny] = temp;
    }

    //최대 사탕 개수 구하는 메서드
    public static int countCandies() {
        int maxLen = 0;
        for(int i = 0; i < N; i++) {
            int rowCnt = 1;
            int colCnt = 1;

            for(int j = 1; j < N; j++) {
                if(board[i][j] == board[i][j - 1]) {
                    rowCnt++;
                } else {
                    maxLen = Math.max(maxLen, rowCnt);
                    rowCnt = 1;
                }

                if (board[j][i] == board[j - 1][i]) {
                    colCnt++;
                } else {
                    maxLen = Math.max(maxLen, colCnt);
                    colCnt = 1;
                }
            }
            maxLen = Math.max(maxLen, rowCnt);
            maxLen = Math.max(maxLen, colCnt);
        }
        return maxLen;
    }
}