[BOJ 3085 - Java] 사탕게임 - 구현문제

문제 정보

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

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

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

3
CCP
CCP
PPC

--> 3

4
PPPP
CYZY
CCPY
PPCC

--> 4

슈도 코드

1. 임포트
2. 메인 메서드 생성
3. 입력에 필요한 변수
   1. 순환 횟수 N
   2. 입력받을 배열 char[][] map
   3. 정답 입력할 ans 변수
4. static 메서드
   1. 전체 행중 가장 높은 점수를 갖는 행
   2. 전체 열중 가장 높은 점수를 갖는 열
   3. 스왑 메서드
5. 이중 반복문을 진입하여 각 위치에서 조건문 수행
   1. if(해당 위치에서 x+1한 값이 map의 길이보다 작고, x+1값과 x값이 같지 않을때) → 위치 스왑 → ans에 Math.max(ans, Math.max(findMaxRow(),findMaxCol()))의 값을 담음
   2. y값도 위와 동일한 로직으로 수행
6. ans출력

주요 규칙

• 색이 칠해진 화살표는 두번 수행되는 구간이다.
• 그러므로 x값과 y값이 증감되는 구간만 교환해서 비교하면 시간 복잡도를 줄일 수 있다.

시간 복잡도

O(N^4)

import java.util.Scanner;

public class 사탕게임_3085 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] map = new char[n][n];
        for (int i = 0; i < n; i++) {
            map[i] = sc.next().toCharArray();
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {  
            for (int j = 0; j < n; j++) {  //N^2
                   if (j + 1 < n && map[i][j] != map[i][j + 1]) {
                    swap(map, i, j, i, j + 1);
                    ans = Math.max(ans, Math.max(findMaxCol(map), findMaxRow(map)));  //2N^2
                    swap(map, i, j, i, j + 1);
                }
                if (i + 1 < n && map[i][j] != map[i + 1][j]) {
                    swap(map, i, j, i + 1, j);
                    ans = Math.max(ans, Math.max(findMaxCol(map), findMaxRow(map)));
                    swap(map, i, j, i + 1, j);
                }
            }
            if(ans==n) break;
        }
        System.out.println(ans);
    }

    public static int findMaxRow(char[][] map) { //N^2
        int N = map.length;
        int maxRow = 0;
        for (int r = 0; r < N; r++) {
            int len = 1;
            for (int c = 1; c < N; c++) {
                if (map[r][c] == map[r][c - 1]) {
                    len++;
                } else {
                    maxRow = Math.max(maxRow, len);
                    len = 1;
                }
            }
            maxRow = Math.max(maxRow, len); //len값이 초기화되기 전에 갱신시켜준다.
        }
        return maxRow;
    }
    public static int findMaxCol(char[][] map) { //N^2
        int N = map.length;
        int maxrow = 0;
        for (int c = 0; c < N; c++) {
            int len = 1;
            for (int r = 1; r < N; r++) {
                if (map[r][c] == map[r-1][c]) {
                    len++;
                } else {
                    maxrow = Math.max(maxrow, len);
                    len = 1;
                }
            }
            maxrow = Math.max(maxrow, len); //len값이 초기화되기 전에 갱신시켜준다.
        }
        return maxrow;
    }
    public static void swap(char[][] map, int r1, int c1, int r2, int c2) {
        char tmp = map[r1][c1];
        map[r1][c1] = map[r2][c2];
        map[r2][c2] = tmp;
    }
}