알고리즘 풀이 - 백준 3085(사탕 게임, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

NxN크기의 칸에 사탕이 각각 나열되어 있을 때, 인접한 사탕을 상호 교환 후 모두 같은 색으로 이루어진 연속된 사탕을 먹을 때, 최대값을 구하는 문제

 

 

2. 풀이

 

NxN의 크기로 각 칸에 사탕이 하나씩 놓여져 있으며 인접한 사탕을 상호 교환 후 하나의 행 또는 열에서 가장 긴 연속된 사탕의 개수를 구하는 문제이다.

여기서, 우리는 2가지의 작업이 수행된다는 것을 알 수 있다.

① 인접한 사탕을 상호 교환한다.
② 행 또는 열에서 가장 긴 연속된 동일 사탕의 개수를 찾는다.

 

여기서 ①의 인접한 사탕을 교환하는 경우의 모든 경우의 수를 알아보자.

 

 

파란 사탕이 인접한 사탕은 붉은 색으로 칠해진 사탕들이다. 그러면 NxN의 사탕이 있으니 각 경우에 모두 인접한 사탕과 교환을 하는 경우 약 $4N^2$의 경우가 있을 것이다.

NxN의 크기이니 $N^2$ 이며, 4번 인접한 것들과 비교하기 때문인데, 물론 가장자리에 있는 사탕은 4번을 모두 하지는 않지만 편의를 위해 위와 같이 계산하였다.

 

그런데 실제로는, 위쪽 좌측에 위치한 사탕부터 인접한 것을 교환한다면 우측 / 아래측의 경우와만 인접 사탕과 교환하면 된다. 왜냐하면 위쪽, 왼쪽은 이미 이전 사탕과의 교환 과정에서 겹치기 때문이다.

따라서, ①의 과정만 수행할 때, 시간복잡도는 $O(2N^2)$ 이다.

 

 

②에서 행 또는 열의 가장 긴 연속된 동일 사탕의 경우를 구하는 경우의 수도 알아보자.

인접한 사탕을 상호 교환 후 이루어지는 과정이므로, ①의 과정이 1회 수행될 때마다 ② 과정이 수행되어야 한다.

 

그런데, 매번 NxN의 모든 행 / 열을 찾을 필요는 없다. 인접한 사탕이 교환되었을 때, 그 영향을 받는 행 / 열만 조사하면 되기 때문이다. 아래의 그림을 보자.

 

 

위 그림과 같이, 아래측 사탕과 교환 시에 영향 받는 행/열, 우측 사탕과 교환 시에 영향 받는 행/열만 수행하면 된다.

그래서, 한 행 또는 한 열을 체크하는 데 수행되는 시간복잡도는 $O(N)$ 이고, 최대 3개의 행, 열을 체크하므로 총 $O(3N)$이 된다.

그러나 코드에서는 편의를 위해 같은 행, 열을 1회씩 더 체크하도록 하였다. 실제로 위 그림 중 좌측 그림이 (y1, x1), (y2, x2)라고 할 때, x1과 x2의 값은 0번째 열로 같으므로 2번 체크할 필요가 없지만 코드에서는 편의상 한 번 더 체크하도록 하였다. 그래서 $O(4N)$이 되었다.

 

따라서 전체 시간복잡도는 어떻게 될까? ①이 수행되는데 $O(2N^2)$ 이고 ②가 수행되는 데 $O(4N)$ 인데, ①이 수행될 때마다 ②가 수행되어야 하므로 전체 시간복잡도는 $O(8N^3)$ 이 된다.

여기서 전체 경우의 수를 대략 구해보면, N이 최대 50이므로 $50*50*50*8 = 1,000,000$ 이 되어 1초에 약 1억개의 연산을 수행할 수 있는 컴퓨터의 입장에서는 완전 탐색으로 수행해도 충분히 빠르게 해결할 수 있는 문제가 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

public class Main{
    static char bomboni[][];
    static int n;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // N 값 읽어들이기
        n = Integer.parseInt(br.readLine());
        
        // bomboni 초기화
        bomboni = new char[n][n];
        for(int i=0; i < n; i++){
            bomboni[i] = br.readLine().toCharArray();
        }
        int max = 0;
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                // 아래측 인접 사탕과 swap 후 체크한 다음 다시 swap
                if(i < n-1){
                    swap(i, j, i+1, j);
                    max = Math.max(max, check(i, j, i+1, j));
                    swap(i, j, i+1, j);    
                }
                
                // 우측 인접 사탕과 swap 후 체크한 다음 다시 swap
                if(j < n-1){
                    swap(i, j, i, j+1);
                    max = Math.max(max, check(i, j, i, j+1));
                    swap(i, j, i, j+1);    
                }
            }
        }
        
        bw.write(String.valueOf(max));
        bw.flush();
        br.close();
    }
    
    // ① 인접한 사탕 교환하는 코드
    private static void swap(int y1, int x1, int y2, int x2){
        char temp = bomboni[y1][x1];
        bomboni[y1][x1] = bomboni[y2][x2];
        bomboni[y2][x2] = temp;
    }
    
    // ② 과정을 수행하는 코드
    private static int check(int y1, int x1, int y2, int x2){
        int max = 0;
        
        int current = 1;
        // y1기준 가로 체크
        for(int i=1; i < n; i++){
             if(bomboni[y1][i] == bomboni[y1][i-1]){
                 current++;
             } else {
                 current = 1;
             }
             // 현재 max값과 비교
             max = Math.max(current, max);
        }
        
        // y2기준 가로 체크
        current = 1;
        for(int i=1; i < n; i++){
             if(bomboni[y2][i] == bomboni[y2][i-1]){
                 current++;
             } else {
                 max = Math.max(current, max);
                 current = 1;
             }
             // 현재 max값과 비교
             max = Math.max(current, max);
        }
        
        // x1기준 세로 체크
        current = 1;
        for(int i=1; i < n; i++){
             if(bomboni[i][x1] == bomboni[i-1][x1]){
                 current++;
             } else {
                 max = Math.max(current, max);
                 current = 1;
             }
             // 현재 max값과 비교
             max = Math.max(current, max);
        }
        
        // x2기준 세로 체크
        current = 1;
        for(int i=1; i < n; i++){
             if(bomboni[i][x2] == bomboni[i-1][x2]){
                 current++;
             } else {
                 max = Math.max(current, max);
                 current = 1;
             }
             // 현재 max값과 비교
             max = Math.max(current, max);
        }
        return max;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.