BOJ 3085. 사탕게임

BOJ 3085. 사탕게임

풀이

NxN 크기의 보드에서 두 칸을 골라 서로 사탕을 교환하고
이때 인접해있는 사탕을 먹는다고 하였을 때
먹을 수 있는 사탕의 최대 개수를 구하는 방법은

보드 전체를 1번씩 확인해보아야 하는데, 아래와 오른쪽을 바꾸어가며 전체 보드를 확인해보면
보드를 모두 1번씩 확인할 수 있다.

이때 시간 복잡도는 O(NN)이다.
최대 주어지는 N의 수는 50이므로 5050은 
1초 안에 수행할 수 있는 경우의 수이므로 모든 경우의 수에 대입하여 정답을 찾아보도록 한다.

swap()하고 check()하여 인접한 사탕의 최대 개수를 구한 후 다시 원래대로 swap() 해준다.

이 과정을 반복하여 최대 개수를 구한다.

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

class Main {
    static Character[][] a;
    static int N;
    static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        a = new Character[N][N];

        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < N; j++) {
                a[i][j] = input.charAt(j);
            }
        }
        br.close();


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (j + 1 < N) {
                    swap(i, j, i, j + 1);
                    check();
                    swap(i, j, i, j + 1);
                }

                if (i + 1 < N) {
                    swap(i, j, i + 1, j);
                    check();
                    swap(i, j, i + 1, j);
                }
            }
        }

        System.out.println(ans);
    }

    static void swap(int startI, int startJ, int endI, int endJ) {
        char temp = a[startI][startJ];
        a[startI][startJ] = a[endI][endJ];
        a[endI][endJ] = temp;
    }

    static void check() {
        for (int i = 0; i < N; i++) {
            int count = 1;
            for (int j = 0; j < N - 1; j++) {
                if (a[i][j] == a[i][j + 1]) {
                    count++;
                } else {
                    ans = Math.max(ans, count);
                    count = 1;
                }
            }
            ans = Math.max(ans, count);
        }

        for (int j = 0; j < N; j++) {
            int count = 1;
            for (int i = 0; i < N - 1; i++) {
                if (a[i][j] == a[i + 1][j]) {
                    count++;
                } else {
                    ans = Math.max(ans, count);
                    count = 1;
                }
            }
            ans = Math.max(ans, count);
        }
    }
} 

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val a = Array(n) { CharArray(n) }
    var ans = 0

    for (i in 0 until n) a[i] = readLine()!!.toCharArray()

    fun swap(startI: Int, startJ: Int, endI: Int, endJ: Int) {
        val temp = a[startI][startJ]
        a[startI][startJ] = a[endI][endJ]
        a[endI][endJ] = temp
    }

    fun check() {
        for (i in 0 until n) {
            var count = 1
            for (j in 0 until n - 1) {
                if (a[i][j] == a[i][j + 1]) {
                    count++
                } else {
                    ans = max(ans, count)
                    count = 1
                }
            }
            ans = max(ans, count)
        }

        for (j in 0 until n) {
            var count = 1
            for (i in 0 until n - 1) {
                if (a[i][j] == a[i + 1][j]) {
                    count++
                } else {
                    ans = max(ans, count)
                    count = 1
                }
            }
            ans = max(ans, count)
        }
    }

    for (i in 0 until n) {
        for (j in 0 until n) {
            if (j + 1 < n) {
                swap(i, j, i, j + 1)
                check()
                swap(i, j, i, j + 1)
            }

            if (i + 1 < n) {
                swap(i, j, i + 1, j)
                check()
                swap(i, j, i + 1, j)
            }
        }
    }

    println(ans)
} 

제출하고 계속 틀려서 반례를 찾아보다 보니
check()에서 count를 1로 초기화 안 해주어서 계속 틀렸었다.  

풀면서 도움이 되었던 반례들


ZCY
ZCP
PYZ
-> 답:2

4
CCCC
YDYD
DYDY
YDYD
-> 답:4

2
CC
YY
-> 답:2

40
YYYYYYYYYCYYYYYYYYYYYYYYYCZZZZZZZYYYYYZC
PYPCYZCPYCZZCCPZYYPZYYYYPPZZPYCCCZYZZZPY
ZPPCYCCPYYZYPPZCZPYCCCZZYYPZZPYPPPPZPCZC
ZCYYZZYCPPPCCYPYYPZZZZCCCCZZCZCYCYZCZZYC
PYZYZZCCZZCCPPYCZPYPPZYZYYYZZPPCCZYYYZCZ
PPPCZZPCCCCCCCCCCCCCCCCCCYCZYYYZCYYCPCPZ
PZYPZYPPYYYZZZPPPZPYZPYZCZZPYZCZZPPCYCCZ
YPPYYYYCCPYPZPCPPPCZCZZYZZZZYYZPZZCCCZYY
YPZCZCPZYYZCCPPPYPPCCPCYZYYYCPPPYCYYCPYC
ZPYZCCZCYZYYCPCCPPYYZPYCCPPCPZCCZCCZYYPY
CPPPCPZZZCYCPYCZYZZPYPZCYYCCZCZZPZYCPZCZ
YZYCYPCPPYPPPPYYYPYPCPCPZZPPCYZCZPZZZZYP
ZCZPYZPPYYYPYPCZYZZYZZPZCZPPPZYCZYPCPYYC
YPZPZYCCYPZZCCPYYCYZYYYYYCZYZZYZZPPYCZCZ
YCZPZCCCCCYCCCCCCCCCCCZYPYZPCZPZZPZZYPYY
YYYYYYYYYYPYYYYYYYYYYYYYYYYYYYYYYYYYYZZP
ZYZCZZCCZPZCZYCPYPCCPYZYCCPPZZCZYCZCYPYP
YYZYPZZYCPCYCZPZYCZPZCCZYCCCZZZYYYZYYPCP
YZZPZYPYCZCPPCZPYCCPYCYZPCCYYZYPCPPPYYPZ
YYZPPZYCZZZYYPYCYZCCYYZPYCCYPZCCZCCCYYZC
CYZZPPCZYZYCCPCYYCPZPPZZPCZZYZZYZZCZYYPC
PPZYZYZPZZZZYPZYYPZPPZPPZCYCPZYZPPYYYYYZ
CZZZYPZYCCYYYPPZYCYPZPCCPCYYYZZYCPYCYCYY
YCZZCZCCYPPYYZYYYPPPZZYYCCCYYZZZYZZZYYCC
YCZPZPPPZPCYYYZZYCPPZYPZYCZZZZZPYYPYCYPC
PCZZZYYZCPCPCZYYYCPYZCCPZCZPYZZPYPZPYZYY
ZZZZPPPPPYZCZCPYYCCCCCCCCCCCYCCCCCCPCCCP
CPYCYZCZCZCYCPCYYCYZCZYYZCCPZZYZPZCPYCCP
YZZYYZZZZPZZCZCYYCZZPYZYCCPCPZYCYCZPYZPZ
YZZZZZZZZZZZZZZZZZZZZZZZCZZZZZZZZZZZZZZZ
YZZPPPPPPPPPPPPPPCPPPPPYYCYCZZZCCPCCYPYZ
YYZCPYPPYZPPYCZPYCZPCPCZZZCYCZYZCPCPZPZZ
CYZPCYYYYYYYYYYYYCYYYYYYYYYYYZYYCYZYPYZC
CPZCCZZZZZZZZZZZZCZZZZZZZZZZYZCCZCPZZCCY
YYZPCPZZCYYYYYCPYCZPYYYPPZZCCZZCPPPPCCPP
YYZZPCCYZCCCYPCYYPZCZZZZZPPYZCCCCCZCPPCY
PYYYYYYYYYYYYYYYYYYYYYYPYCZZPPYZYPPPPYCC
YPZCZPZYPZPPCYCZYCYPCCCZCZZCCZYZYYCYYZCZ
CPPZZPCYYCCCYCCPZPYYZYCYZYZYPYCPPZPCPCYC
ZPCYPYZPPCYYPYZZZPPZZZCCPYCYPCYYCYPPYCZY
답->37

4
CCCP
CCCP
CCCP
CCCP
답->4

3
YCP
CCY
YPC
답->3

6
CCYYCC
YYCCYY
CCYYCC
YYCCYY
CCYYCC
YYCCYY
답->3

5
CPZCC
ZYCPZ
CYYPZ
ZPZCC
CCPYY
답->3

풀이소스

github.com/beomjo/algorithm-study/commit/e4e7351efb5ef9f438a76f09dad56eca441ef02d