[BOJ] 3085번: 사탕 게임

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

3085번: 사탕 게임

 

 

 

1. 문제 설명 

N * N 크기에 사탕이 모두 채워진다. 사탕의 색이 다른 인접한 두 칸을 골라 서로 교환한 후에 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 구하라. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하라.

 

 

 

2. 접근 방식 및 시간복잡도

이중 for문을 돌면서 해당 위치(i, j)의 사탕을 (i, j+1)의 사탕과 교환 후 행 기준 연속된 사탕의 개수, 열 기준 연속된 사탕의 개수를 계산하고 바꾼 사탕을 다시 되돌려놓고, (i, j)의 사탕을 이번에는 (i+1, j)의 사탕과 교환 후 위의 계산을 반복해주고 다시 되돌려놓는 식으로 문제를 풀었다. 3 <= N <= 50 이라서 N^2 * N^2 = 6,250,000 이라 충분히 통과가능하다.

 

시간복잡도 : O(N^4)

 

 

3. 내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static int[][] grid;
    static int N, result = Integer.MIN_VALUE;
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        grid = new int[N][N];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                int num = charToInt(str.charAt(j));
                grid[i][j] = num;
            }
        }
    }
    private static int charToInt(char ch) {
        if (ch == 'C') {
            return 1;
        } else if (ch == 'P') {
            return 2;
        } else if (ch == 'Z') {
            return 3;
        } else {
            return 4;
        }
    }
    static int fillGridRow(int[][] grid, int startRow, int endRow) {
        int ans = 1;
        for (int i = startRow; i <= endRow; i++) {
            // 배열 안에서 초기화
            int cnt = 1;
            for (int j = 1; j < N; j++) {
                if (grid[i][j] == grid[i][j - 1]) {
                    cnt++;
                }
                else cnt = 1;
                ans = Math.max(ans, cnt);
            }
        }
        return ans;
    }
    static int fillGridCol(int[][] grid, int startCol, int endCol) {
        int ans = 1;
        for (int j = startCol; j <= endCol; j++) {
            // 배열 안에서 초기화
            int cnt = 1;
            for (int i = 1; i < N; i++) {
                if (grid[i][j] == grid[i - 1][j]) {
                    cnt++;
                }
                else cnt = 1;
                ans = Math.max(ans, cnt);
            }

        }
        return ans;
    }
    static void pro() {
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (y + 1 < N) {
                    int tmp = grid[x][y]; grid[x][y] = grid[x][y + 1]; grid[x][y + 1] = tmp;
                    result = Math.max(result, Math.max(fillGridRow(grid, x, x), fillGridCol(grid, y, y+1) ));
                    tmp = grid[x][y]; grid[x][y] = grid[x][y + 1]; grid[x][y + 1] = tmp;
                }
                if (x + 1 < N) {
                    int tmp = grid[x][y]; grid[x][y] = grid[x+1][y]; grid[x+1][y] = tmp;
                    result = Math.max(result, Math.max(fillGridRow(grid, x,x+1), fillGridCol(grid, y, y) ));
                    tmp = grid[x][y]; grid[x][y] = grid[x+1][y]; grid[x+1][y] = tmp;
                    }
                }
            }
        }

    public static void main(String[] args) throws IOException{
        input();
        pro();
        System.out.println(result);
    }
}

 

 

4. 느낀 점

아이디어를 빠르게 캐치해서 실수없이 정확하게 작성하는 연습을 하자.