BOJ 3085 사탕 게임 (Java)

문제 탐색하기

• N×N크기에 사탕을 채워 놓는다.
• 사탕의 색은 모두 같지 않을 수도 있다.
• 사탕의 색이 다른 인접한 두 칸을 골라 교환한다.
• 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열) 을 고른 다음 그 사탕을 모두 먹는다.
• 정답으로 먹을 수 있는 사탕의 최대 개수를 구한다.

코드 설계하기

구현 방법

• N(3 ≤ N ≤ 50)이 크지 않아서, 가능한 전체 경우를 탐색해도 무방하다. (=> Brute Force)
• 가로, 세로 방향 두가지 경우에 대해 모두 검사해서, 최댓값 갱신하는 방식으로 풀이
  • 연속된 사탕 개수를 검사한다.
• 참고한 풀이

시간 복잡도

1. 모든 인접 칸 쌍에 대해 swap 시도
   • 가로 방향: 총 N×(N−1) 쌍
   • 세로 방향: 총 (N−1)×N 쌍
   • 총 2×N×(N−1) ≈ O(N²) ≈ O(N²)
2. swap 후 countMaxCandies 실행
   • swapAndCalc() 함수 내부
     • 가로 한 줄씩 → 최대 N줄 × N칸 → O(N²)
     • 세로 한 줄씩 → 최대 N줄 × N칸 → O(N²)

• O(N²)×O(N²)=O(N⁴)

문제 풀이 (Java)

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class b3085 {  
    static int N;  
    static int maxCandies;  
    static char[][] charBoard;  
    public static void main(String[] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
        N = Integer.parseInt(br.readLine());  
        charBoard = new char[N][N];  
        maxCandies = 0;  
  
        for(int i = 0; i < N ; i++){  
            String tmp = br.readLine();  
            for(int j = 0; j < N ; j++){  
                // Board 초기화    
charBoard[i][j] = tmp.charAt(j);  
            }  
        }  
  
        // 가로 방향 검사    
for(int i = 0; i < N ; i++){  
            for(int j = 0; j < N - 1 ; j++){  
                swapAndCalc(i, j, i, j+1);  
            }  
        }  
  
        // 세로 방향 검사    
for(int i = 0; i < N - 1 ; i++){  
            for(int j = 0; j < N ; j++){  
                swapAndCalc(i, j, i+1, j);  
            }  
        }  
  
        System.out.println(maxCandies);  
    }  
  
    private static void swapAndCalc(int i, int j, int i1, int i2) {  
        // swap  i.j <-> i1.j1  
        char tmp = charBoard[i][j];  
        charBoard[i][j] = charBoard[i1][i2];  
        charBoard[i1][i2] = tmp;  
  
        int currentCandies = countMaxCandies();  
  
        // 최댓값 갱신    
if(maxCandies < currentCandies) {  
            maxCandies = currentCandies;  
        }  
  
        // 원위치로    
tmp = charBoard[i][j];  
        charBoard[i][j] = charBoard[i1][i2];  
        charBoard[i1][i2] = tmp;  
    }  
  
    // 현재 board에서 최대 사탕 개수 계산    
private static int countMaxCandies() {  
        int maxcnt = Integer.MIN_VALUE;  
  
        // 가로 방향으로 연속된 사탕 개수 계산    
for (int i = 0; i < charBoard.length; i++) {  
            int count = 1;  
            for (int j = 1; j < charBoard.length; j++) {  
                // 연속되는 경우에 +1하고, 그렇지 않으면 초기화    
if (charBoard[i][j] == charBoard[i][j - 1]) {  
                    count++;  
                } else {  
                    count = 1;  
                }  
  
                // 최대 개수 갱신    
if(maxcnt < count) maxcnt = count;  
  
            }  
        }  
  
        // 세로 방향으로 연속된 사탕 개수 계산    
for (int i = 0; i < charBoard.length; i++) {  
            int count = 1;  
            for (int j = 1; j < charBoard.length; j++) {  
                // 연속되는 경우에 +1하고, 그렇지 않으면 초기화    
if (charBoard[j][i] == charBoard[j - 1][i]) {  
                    count++;  
                } else {  
                    count = 1;  
                }  
  
                // 최대 개수 갱신    
if(maxcnt < count) maxcnt = count;  
            }  
        }  
  
        return maxcnt;  
    }  
  
}