[BOJ] 3085 사탕게임 - JAVA

1. 문제

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

3085번: 사탕 게임

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

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

---

2. 풀이

위에서부터 오른쪽으로 swap처음위치를 바꾸기 때문에 nr,nc는 항상 아래쪽과 오른쪽만 보면 된다.

N 범위에 들어오고 바꾸려는 요소가 이전과 같지 않다면 교환하고, 이 상태에서 가장 많이 사탕을 먹을 수 있는 개수가 몇개인지 센다. 

다 센 뒤에 지역변수 max와 비교한다. (이건 없어도 될것같다. 어차피 전역변수 result가 있으니까 바로바로 비교해줘도 된다.)

swap한 요소를 제자리로 돌려놓는다.

사탕개수를 체크할 때, 같은 열, 같은 행만 체크하면 되기 때문에 한 번에 썼다. [i][j] 위치만 바꿔주면 된다. 비교하다가 다른 요소가 나오면 cnt를 1로 하고 다시 비교를 시작한다.

import java.io.*;

public class BOJ_3085_사탕게임 {
    static int N,result;
    static char[][] board;
    static int[][] deltas = {{1,0},{0,1}};//아래쪽-오른쪽
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(in.readLine());
        board = new char[N][N];

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

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                result = Math.max(result,swapCandy(i,j));
            }
        }

        System.out.println(result);
    }

    private static int swapCandy(int r, int c) {
        int max = 0;

        for(int d=0;d<2;d++){
            int nr = r+deltas[d][0];
            int nc = c+deltas[d][1];
            if(nr>=0 && nr<N && nc>=0 && nc<N && board[r][c]!=board[nr][nc]){
                char tmp = board[r][c];
                board[r][c] = board[nr][nc];
                board[nr][nc] = tmp;

                max = Math.max(max,countCandy());

                board[nr][nc] = board[r][c];
                board[r][c] = tmp;
            }
        }
        return max;
    }

    private static int countCandy(){
        int tmpMax = 1;
        for(int i=0;i<N;i++){
            char nowH = board[i][0];
            char nowV = board[0][i];
            int cntH = 1;
            int cntV = 1;

            for(int j=1;j<N;j++){
                if(nowH!=board[i][j]){
                    tmpMax = Math.max(tmpMax,cntH);
                    nowH = board[i][j];
                    cntH = 1;
                }
                else ++cntH;

                if(nowV != board[j][i]){
                    tmpMax = Math.max(tmpMax,cntV);
                    nowV = board[j][i];
                    cntV = 1;
                }
                else ++cntV;

            }
            tmpMax = Math.max(tmpMax,cntH>cntV?cntH:cntV);
        }

        return tmpMax;
    }
}

 

---

3. 결과