[자바]백준 3085번 사탕게임[브루트포스][엄탱]

문제 링크

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

3085번: 사탕 게임

문제 설명

해당 문제는 아래와 같은데 잘 이해가 안 되었다.

N x N 크기의 보드에 사탕을 채워 놓았고 사탕의 4가지 색상 중 어느 것이든 놓일 수 있다. 이때, 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

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

 

여기서 파란색으로 칠한 곳이 이해가 되지 않았다.

인접한 두 칸을 상하좌우 다 변경이 가능한 건지, 교환한 상태 그대로 내버려두고 그다음 행이나 열로 넘어가는 건지 몰랐기 때문이다.

 

결론은, 두 칸을 상하 좌우 다 변경이 가능하고 교환은 한 번만 하고 가장 긴 행이나 열을 찾는 것이다. 즉, 교환한 상태로 내버려두고 다음 행이나 열을 검색하는 게 아니라 교환한 것은 다시 돌려놔야 하는 것이다.

 

해석은 이쯤 하고 다음 문제 풀이로 넘어가자. 

문제 풀이

문제 풀이는 무식하게 생각하면 간단하나 어떻게 풀어야 잘 풀까 생각할수록 풀이가 어려워진다.

그럼 간단하게 무식하게 생각해 보자

• 인접한(행 혹은 열 다 포함) 사탕끼리 색을 바꿔준다.
• 가장 긴 수열을 찾아준다.
• 바꿔준 사탕의 색을 돌려준다.

위의 3가지만 해주면 된다. 하지만 어떻게?? 무식하게!!

• 행을 기준으로 오른쪽으로 탐색하면서 오른쪽 색상과 현재 색상을 바꿔주고 탐색하고 다시 돌려주기
• 열을 기준으로 아래쪽으로 탐색하면서 아래쪽 색상과 현재 색상을 바꿔주고 탐색하고 다시 돌려주기
• 행을 기준으로 왼쪽과 색을 변경해 줄 필요 없고 열을 기준으로 위쪽과 색을 변경해줄 필요 없다. 오른쪽 아래쪽을 바꿔가면서 변경했기 때문에 이미 바꿔줬던 색상이기 때문이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        N = Integer.parseInt(br.readLine());

        board = new char[N][N];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            
            for (int j = 0; j < N; j++) {
                board[i][j] = s.charAt(j);
            }
        }
        
        // 행을 기준으로 오른쪽 색과 변경
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - 1; j++) {
                swap(i, j, i, j + 1);
                search();
                swap(i, j + 1, i, j);
            }
        }
        
        // 열을 기준으로 아래쪽 색과 변경
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N; j++) {
                swap(i, j, i + 1, j);
                search();
                swap(i + 1, j, i, j);
            }
        }
        
        System.out.println(max);
        br.close();
    }
    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;
    }
    
    public static void search() {
    	// 행에서 긴 수열 탐색
        for (int i = 0 ; i < N; i ++) {
            int count = 1;
            
            for (int j = 0; j < N - 1; j++) {
                if (board[i][j] == board[i][j + 1]) {
                    count++;
                    max = Math.max(count, max);
                } else {
                    count = 1;
                }               
            }
        }
        
        // 열에서 긴 수열 탐색
        for (int i = 0 ; i < N; i ++) {
            int count = 1;
            
            for (int j = 0; j < N - 1; j++) {
                if (board[j][i] == board[j + 1][i]) {
                    count++;
                    max = Math.max(count, max);
                } else {
                    count = 1;
                }               
            }
        }
    }
}