[백준] 사탕 게임

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

문제 정리

각 Row, Column에 따라 연속된 문자의 개수 구하기
이때 붙어있는 것끼리 교환할 수 있다.

시간복잡도

• 모든 칸 오른쪽, 아래쪽 교환 - 2 x N^2
• 교환마다 검사 2 * N^2
• 총 O(N^4) N은 최대 50

풀이 과정

교환했을 경우 어떻게 되었는지에 대한 코드가 필요하다.

• 시작은 왼쪽 위 상단부터 시작해서 오른쪽 하단으로 간다

• 그렇기에, 현재 위치에서의 오른쪽 또는 아랫쪽의 교환 시 발생하는 개수에 대해 확인

• 필요한 부분 코드

  • swap 함수 - swap()
  • 오른쪽과 교환
  • 아랫쪽과 교환
  • row, column 기준으로 개수 세기 - RowColumnCount()

위 기준으로 크게 잡고 코드를 구성하면 된다.

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

public class Main {

    static char[][] board;
    static int n;
    static int res;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        board = new char[n+3][n+3];
        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);
                    RowColumnCount();
                    swap(i, j, i, j+1);
                }

                // 밑에와 교환
                if (i < n - 1) {
                    swap(i, j, i+1, j);
                    RowColumnCount();
                    swap(i, j, i+1, j);
                }
            }
        }

        System.out.println(res);
    }

    public static void RowColumnCount() {

        // row 개수
        for(int i = 0; i < n; i++) {
            int cnt = 1;
            for (int j = 0; j < n-1; j++) {
                if (board[i][j] == board[i][j+1]) cnt++;
                else {
                    res = Math.max(res, cnt);
                    cnt = 1;
                }
            }
            res = Math.max(res, cnt);
        }

        // col 개수
        for(int j = 0; j < n; j++) {
            int cnt = 1;
            for(int i = 0 ; i < n-1; i++) {
                if (board[i][j] == board[i+1][j]) cnt++;
                else {
                    res = Math.max(res, cnt);
                    cnt = 1;
                }
            }
            res = Math.max(res, cnt);
        }
    }

    public static void swap(int x1, int y1, int x2, int y2) {
        char temp = board[x1][y1];
        board[x1][y1] = board[x2][y2];
        board[x2][y2] = temp;
    }
}

생각해내는 것은 쉬웠는데, 구현이 다소 까다로웠다.