21.04.01 - [BOJ] 3085. 사탕 게임

[suhyunsim]

문제

• 3085

핵심 아이디어

• N * N 테이블 (N <= 50)
• 인접한 두 칸을 고르고, 사탕을 교환: N^2 * 2
• 가장 긴 연속 부분 행 또는 열 찾기: N^2
  
  => 임의의 두 칸을 변경했을 때 정답에 변화 있는 것은 최대 3개의 행과 열: O(3N) = O(N)
• O(N^3)으로도 풀이할 수 있음
• 50 ^ 4 = 6250000이라 O(N^4) 이어도 가능

어려운 점, 실수

풀이

• O(N^4) 풀이

package main.java.com.poogle.BOJ.Q3085;

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        String[][] candies = new String[n][n];
        for (int i = 0; i < n; i++) {
            candies[i] = br.readLine().split("");
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //행 확인
                if (j + 1 < n) {
                    //Swap
                    String swap = candies[i][j];
                    candies[i][j] = candies[i][j + 1];
                    candies[i][j + 1] = swap;
                    //몇 개인지 세기
                    int tmp = check(candies);
                    if (ans < tmp) ans = tmp;
                    //돌려놓기
                    swap = candies[i][j];
                    candies[i][j] = candies[i][j + 1];
                    candies[i][j + 1] = swap;
                }
                //열 확인
                if (i + 1 < n) {
                    String a = candies[i][j];
                    candies[i][j] = candies[i + 1][j];
                    candies[i + 1][j] = a;
                    //몇 개인지 세기
                    int tmp = check(candies);
                    if (ans < tmp) ans = tmp;
                    //돌려놓기
                    a = candies[i][j];
                    candies[i][j] = candies[i + 1][j];
                    candies[i + 1][j] = a;
                }
            }
        }
        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    private static int check(String[][] candies) {
        int n = candies.length;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            int cnt = 1;
            for (int j = 1; j < n; j++) {
                if (candies[i][j].equals(candies[i][j - 1])) {
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt) ans = cnt;
            }
            cnt = 1;
            for (int j = 1; j < n; j++) {
                if (candies[j][i].equals(candies[j - 1][i])) {
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt) ans = cnt;
            }
        }
        return ans;
    }
}

• O(N^3) 풀이

package main.java.com.poogle.BOJ.Q3085;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] candies = new char[n][n];
        for (int i = 0; i < n; i++) {
            candies[i] = sc.next().toCharArray();
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //행 확인
                if (j + 1 < n) {
                    //Swap
                    char t = candies[i][j];
                    candies[i][j] = candies[i][j + 1];
                    candies[i][j + 1] = t;
                    //몇 개인지 세기
                    int tmp = check(candies, i, i, j, j + 1);
                    if (ans < tmp) ans = tmp;
                    //돌려놓기
                    t = candies[i][j];
                    candies[i][j] = candies[i][j + 1];
                    candies[i][j + 1] = t;
                }
                //열 확인
                if (i + 1 < n) {
                    char t = candies[i][j];
                    candies[i][j] = candies[i + 1][j];
                    candies[i + 1][j] = t;
                    //몇 개인지 세기
                    int tmp = check(candies, i, i + 1, j, j);
                    if (ans < tmp) ans = tmp;
                    //돌려놓기
                    t = candies[i][j];
                    candies[i][j] = candies[i + 1][j];
                    candies[i + 1][j] = t;
                }
            }
        }
        System.out.println(ans);
    }

    //start, end, row, column
    private static int check(char[][] candies, int sr, int er, int sc, int ec) {
        int n = candies.length;
        int ans = 1;
        for (int i = sr; i <= er; i++) {
            int cnt = 1;
            for (int j = 1; j < n; j++) {
                if (candies[i][j] == candies[i][j - 1]) {
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt) ans = cnt;
            }
        }
        for (int i = sc; i <= ec; i++) {
            int cnt = 1;
            for (int j = 1; j < n; j++) {
                if (candies[j][i] == candies[j - 1][i]) {
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt) ans = cnt;
            }
        }
        return ans;
    }
}