3085번: 사탕 게임

문제

N x N 크기에 사탕이 채워져 있습니다. 사탕의 색이 다른 인접한 두 칸을 골라 서로 교환합니다. 그 다음, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고르는 프로그램을 작성하는 문제입니다.

• 입력: 배열의 크기 N (3 ≤ N ≤ 50), N개의 줄에 걸쳐 보드에 채워져 있는 사탕의 색상 정보가 주어집니다.
• 출력: 상근이가 먹을 수 있는 사탕의 최대 개수를 출력합니다.

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

풀이: 완전 탐색과 스왑(Swap) 롤백

N이 최대 50으로 매우 작기 때문에, 모든 인접한 칸을 한 번씩 다 바꾸어 보고 매번 최대 사탕 개수를 세는 전형적인 완전 탐색(Brute Force) 문제입니다. 

• 초기 상태 검사: 사탕을 교환하기 전 원래 상태에서도 가장 긴 연속 부분이 정답일 수 있으므로, 입력을 받은 직후 초기 상태에서 check() 메서드를 한 번 호출합니다.
• 인접 사탕 교환 (swap): 이중 반복문을 돌며 현재 위치 (i, j)를 기준으로 우측과 하단의 사탕을 교환합니다. 코드를 깔끔하게 만들기 위해 두 좌표를 넘기면 배열의 값을 바꿔주는 swap 메서드를 만들었습니다.
• 최댓값 갱신 (check 메서드):
  • 행과 열의 검사 로직은 배열의 인덱스 순서만 다를 뿐 구조가 완벽히 동일하므로 하나의 반복문 안에서 동시에 처리할 수 있습니다.
  • yCnt와 xCnt 변수를 두어 이전 캔디와 색상이 같으면 각각 증가시키고, 다르면 1로 초기화함과 동시에 전체 최댓값 ans를 갱신합니다.
  • 한 줄(행 또는 열)의 끝까지 캔디 색상이 같을 경우를 대비하여, 내부 반복문이 끝난 직후 ans = Math.max(ans, Math.max(yCnt, xCnt))를 통해 마지막으로 한 번 더 갱신을 보장합니다.
• 원상 복구 (백트래킹): 검사가 끝난 후에는 다음 탐색에 영향을 주지 않도록 스왑했던 두 칸을 다시 한 번 swap() 하여 원래 상태로 되돌립니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, ans;
    static char[][] a;

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

        n = Integer.parseInt(br.readLine());
        a = new char[n][n];
        for (int i = 0; i < n; i++) {
            a[i] = br.readLine().toCharArray();
        }

        // 초기 상태에서의 최댓값 확인
        check();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 1. 하단 사탕과 교환 후 원상 복구
                if (i != n - 1) {
                    swap(i, j, i + 1, j);
                    check();
                    swap(i, j, i + 1, j);
                }
                
                // 2. 우측 사탕과 교환 후 원상 복구
                if (j != n - 1) {
                    swap(i, j, i, j + 1);
                    check();
                    swap(i, j, i, j + 1);
                }
            }
        }

        bw.write(ans + "");
        bw.flush();
    }

    // 배열 전체를 탐색하여 가장 긴 연속 부분의 길이를 갱신하는 메서드
    static void check() {
        for (int i = 0; i < n; i++) {
            int yCnt = 1;
            int xCnt = 1;
            for (int j = 1; j < n; j++) {
                // 행 검사
                if (a[i][j] == a[i][j - 1]) {
                    yCnt++;
                } else {
                    ans = Math.max(ans, yCnt);
                    yCnt = 1;
                }

                // 열 검사
                if (a[j][i] == a[j - 1][i]) {
                    xCnt++;
                } else {
                    ans = Math.max(ans, xCnt);
                    xCnt = 1;
                }
            }

            // 한 줄 검사가 끝난 후 최종 갱신
            ans = Math.max(ans, Math.max(yCnt, xCnt));
        }
    }

    // 두 좌표의 값을 교환하는 헬퍼 메서드
    static void swap(int y1, int x1, int y2, int x2) {
        char tmp = a[y1][x1];
        a[y1][x1] = a[y2][x2];
        a[y2][x2] = tmp;
    }
}

알고리즘 분류

완전 탐색 (Brute Force), 구현 (Implementation)