[백준] 3085번 - 사탕 게임 (!) (JAVA)

[백준] 3085번 - 사탕 게임 (!) (JAVA)

---

[접근 방법]

브루트포스 알고리즘 방식으로 모든 경우의 수를 고려해야 한다.

1. 변형 전( 사탕 교환이 발생하기 전 ), 주어진 보드에서 사탕 최대 개수(max)를 구한다.

2. 보드의 각 칸과 인접한 칸의 사탕을 교환 하며 사탕 최대 개수를 갱신한다.

---

[JAVA 코드]

// 3085번 - 사탕 게임
import java.util.*;
import java.io.*;

public class Main {

    static int max = 1 , N = 0;
    static char arr[][];

    // (x1, y1) <=> (x2, y2)
    public static void SWAP(int x1, int y1, int x2, int y2){
        char temp = arr[x1][y1];
        arr[x1][y1] = arr[x2][y2];
        arr[x2][y2] = temp;
    }

    // 행 탐색 기준 최댓값 (x행)
    public static int rowMax(int x){
        int temp = 1, res = 1;
        char c = arr[x][0];
        for(int i=1; i<N; i++){

            /*
             * 이전 색과 다른 색인 경우
             * : 기존 최댓값(res) 와 현재값(temp) 비교 후 
             * 최댓값 갱신
             * 
             * 이전과 같은 색인 경우
             * : 현재값(temp)을 계속하여 세어나감
            */

            if (c != arr[x][i]){
                c = arr[x][i];
                res = Math.max(res, temp);
                temp = 1;
            }
            else {
                temp ++;
            }
        }
        return Math.max(res , temp);
    }

    // 열 탐색 기준 최댓값 (y열)
    public static int columnMax(int y){
        int temp = 1, res = 1;
        char c = arr[0][y];
        for(int i=1; i<N; i++){

            if (c != arr[i][y]){
                c = arr[i][y];
                res = Math.max(res, temp);
                temp = 1;
            }
            else {
                temp ++;
            }
        }
        return Math.max(res, temp);
    }
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        arr = new char[N][N];
        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<N; j++){
                arr[i][j] = str.charAt(j);
            }
        }

        // 1. 변경 전 보드의 최댓값 구하기

        // SWAP 전 기존 보드에서 row 기준 최댓값
        for(int i=0; i<N; i++){
            max = Math.max(max, rowMax(i));
        }

        // SWAP 전 기존 보드에서 column 기준 최댓값
        for(int i=0; i<N; i++){
            max = Math.max(max, columnMax(i));
        }

        // 2. 모든 경우 SWAP을 진행 후 최댓값 갱신
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){

                if (j+1 < N){
                    // (i, j) 의 오른쪽에 위치한 (i, j+1)와 SWAP
                    SWAP(i, j, i, j + 1); // (i, j) <=> (i, j+1)
                    max = Math.max(max, rowMax(i));
                    max = Math.max(max, columnMax(j));
                    max = Math.max(max, columnMax(j+1));
                    SWAP(i, j, i, j + 1); // 원상태 보드로 복귀
                }

                if (i+1 < N){
                    // (i, j) 의 아래쪽에 위치한 (i+1, j)와 SWAP
                    SWAP(i, j, i+1, j);
                    max = Math.max(max, rowMax(i));
                    max = Math.max(max, rowMax(i+1));
                    max = Math.max(max, columnMax(j));
                    SWAP(i, j, i+1, j);
                }
            }
        }

        // 3. 최댓값 출력
        bw.write(max + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

---

[Rewind]

 

1. 어려웠던 점

- 열 / 행 기준 최댓값을 구하는 함수를 구축하는 것이 어려웠다.

 

2. 알게된 점

- 실행 함수(main) 밖에 선언된 static 변수가 이미 선언되었다면, main 동명의 함수를 재 선언 하면 안된다.

=> main 밖에 선언된 함수내 변수에 영향을 받지 못한다.

 

3. 개선 방향

- 비슷한 문제를 여러개 풀어야 한다.