[JAVA] 백준 3085 완전탐색

 

 

 

3085번: 사탕 게임

문제

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

풀이

어떻게 풀까 고민하다가 보드의 크기가 50이하로 작고 다른 생각이 떠오르지 않았기 때문에 완전탐색으로 모든 경우의 수를 체크해보았습니다.

모든 인접한 위치의 사탕을 바꾸고 확인해봐도 되지만 아래와 우측만 교체하여 비교하더라도 모든 경우의 수를 체크할 수 있기 때문에 아래와 우측만 교환하여 비교하고 다시 제자리로 돌리고를 반복했습니다.

• 1, 1에서 왼쪽과 위쪽으로 교체하지 않아도 되는 이유는 1,0에서 우측, 0, 1에서 아래를 교체했을 때와 동일한 상황이기 때문입니다.

📌 사탕 교체

    static public void swap(int x, int y, int x2, int y2){
        char temp = A[x][y];
        A[x][y] = A[x2][y2];
        A[x2][y2] = temp;
    }

• 사탕의 위치를 교체하기 위한 메서드입니다.

📌 세로를 기준으로 얼마나 많은 사탕을 먹을 수 있는지 체크

    static public void checkCol(int col){
        int max = 1;
        int current = 1;
        char value = A[1][col];
        for(int i=2; i<N; i++){
            if(value != A[i][col]){
                current = 1;
                value = A[i][col];
            }else{
                current++;
                max = Math.max(max, current);
            }
        }
        answer = Math.max(answer, max);
    }

• 첫 번째 값으로 시작해서 같은 값이 나온다면 current 값을 높여주고 max와 비교하여 큰 값을 갱신합니다.
• 만약 다른 값이 나온다면 current와 value(이어지는 값)을 초기화해줍니다.
• 마지막으로 먹을 수 있는 사탕의 최대값을 전체 기준 최대값과 비교하여 값을 갱신해줍니다.

📌 가로를 기준으로 얼마나 많은 사탕을 먹을 수 있는지 체크

    static public void checkRow(int row){
        int max = 1;
        int current = 1;
        char value = A[row][1];
        for(int i=2; i<N; i++){
            if(value != A[row][i]){
                current = 1;
                value = A[row][i];
            }else{
                current++;
                max = Math.max(max, current);
            }
        }
        answer = Math.max(answer, max);
    }

• 가로 기준도 세로와 동일하게 값을 체크해주고 전체 기준 최대값을 갱신해줍니다.

📌 위의 메서드들을 종합하여 만든 로직

        for(int i=1; i<N; i++){
            for(int j=1; j<N; j++){
                if(j < N-1) {
                    swap(i, j, i, j + 1);
                    checkCol(j);
                    checkCol(j+1);
                    checkRow(i);
                    swap(i, j, i, j + 1);
                }
                // 아래랑 교환
                if(i < N-1){
                    swap(i, j, i+1, j);
                    checkCol(j);
                    checkRow(i+1);
                    checkRow(i);
                    swap(i, j, i+1, j);
                }
            }
        }
        System.out.println(answer);

• i와 j 즉, 현재 진행하고 있는 공간이 오른쪽 혹은 아래가 array 밖이어서 교체를 할 수 없는 경우를 걸러주었습니다.
• 첫 번째 if문 (우측 교체)
  • 현재 값을 가로로 교체합니다.
  • 가로로 교체한 후 j 위치의 세로 체크와 j + 1(우측 교체) 위치의 세로 체크, 현재 가로인 i에서 값들을 체크해줍니다.
  • 이후 다음 칸을 체크하기 위해 값을 제자리로 교체합니다.
• 두 번째 if문 (아래로 교체)
  • 현재 값을 기준으로 아래와 교체합니다.
  • 아래와 교체한 후 현재 열인 j열을 체크하고, 현재 위치 i행과 교체된 위치 i+1 행을 체크하여 줍니다.
  • 이후 다음 칸을 교체하기 위해 값을 제자리로 교체합니다.

전체 경우의 수를 체크한 후 최대값을 출력합니다.

📌 전체 코드

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

public class Main {
    static int N;
    static char[][] A;
    static int answer = 1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine())+1;
        A = new char[N][N];

        for(int i=1; i<N; i++){
            String value = br.readLine();
            for(int j=1;j<N; j++){
                A[i][j] = value.charAt(j-1);
            }
        }

        for(int i=1; i<N; i++){
            for(int j=1; j<N; j++){
                if(j < N-1) {
                    swap(i, j, i, j + 1);
                    checkCol(j);
                    checkCol(j+1);
                    checkRow(i);
                    swap(i, j, i, j + 1);
                }
                // 아래랑 교환
                if(i < N-1){
                    swap(i, j, i+1, j);
                    checkCol(j);
                    checkRow(i+1);
                    checkRow(i);
                    swap(i, j, i+1, j);
                }
            }
        }
        System.out.println(answer);
    }

    // 세로
    static public void checkCol(int col){
        int max = 1;
        int current = 1;
        char value = A[1][col];
        for(int i=2; i<N; i++){
            if(value != A[i][col]){
                current = 1;
                value = A[i][col];
            }else{
                current++;
                max = Math.max(max, current);
            }
        }
        answer = Math.max(answer, max);
    }
    // 가로
    static public void checkRow(int row){
        int max = 1;
        int current = 1;
        char value = A[row][1];
        for(int i=2; i<N; i++){
            if(value != A[row][i]){
                current = 1;
                value = A[row][i];
            }else{
                current++;
                max = Math.max(max, current);
            }
        }
        answer = Math.max(answer, max);
    }

    static public void swap(int x, int y, int x2, int y2){
        char temp = A[x][y];
        A[x][y] = A[x2][y2];
        A[x2][y2] = temp;
    }
}

결과