[BOJ][⚪2][백준#03085] 사탕 게임

문제 출처

BAEKJOON Online Judge #3085

문제

상근이는 어렸을 적에 “봄보니 (Bomboni)” 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50) 다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다. 사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제

예제 1

입력

3
CCP
CCP
PPC

출력

3

예제 2

입력

4
PPPP
CYZY
CCPY
PPCC

출력

4

예제 3

입력

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

출력

4

My Sol

def main():
    def copy_mat():
        return [lst[:] for lst in mat]

    def calc_longest(mat):
        maxx = 1
        for lst in mat:
            ret = calc_length(lst)
            if maxx < ret: maxx = ret

        for j in range(N):
            lst = []
            for i in range(N):
                lst.append(mat[i][j])
            ret = calc_length(lst)
            if maxx < ret: maxx = ret
        return maxx

    def calc_length(lst):
        maxx = 1
        i = 1
        cur = 1
        while i < N:
            if lst[i] == lst[i-1]:
                cur += 1
            else:
                if maxx < cur: maxx = cur
                cur = 1
            i += 1

        return max(maxx, cur)

    def all_change():
        maxx = 1
        for i in range(N):
            for j in range(N-1):
                if mat[i][j] == mat[i][j+1]: continue
                copyed_mat = copy_mat()
                copyed_mat[i][j], copyed_mat[i][j+1] = copyed_mat[i][j+1], copyed_mat[i][j]
                ret = calc_longest(copyed_mat)
                if maxx < ret: maxx = ret
                if maxx == N: return N

        for i in range(N-1):
            for j in range(N):
                if mat[i][j] == mat[i+1][j]: continue
                copyed_mat = copy_mat()
                copyed_mat[i][j], copyed_mat[i+1][j] = copyed_mat[i+1][j], copyed_mat[i][j]
                ret = calc_longest(copyed_mat)
                if maxx < ret: maxx = ret
                if maxx == N: return N

        return maxx


    N = int(input())
    mat = [list(input()) for _ in range(N)]
    return all_change()

print(main())

굉장히 러프한 백트래킹 방식으로 대부분의 경우를 대입하여 문제를 풀었다.

1. 입력을 받는다.
2. 상하좌우로 변경할 수 있지만, 다시 말하면 우측, 그리고 하단과 변경하는 경우만 고려하면 되었다. 왜냐하면 상단과 좌측이라면 이미 이전에서 하고 넘어갔을 것이기 때문이다.
3. 자리를 변경하려는 두 값이 같다면 변경을 진행할 필요가 없다. 똑같을 것이기 때문이다.
4. 자리를 변경할 때 2차원 배열 mat은 깊은 복사를 하여 변경해야 한다. 원래 입력으로 받았던 mat을 깊은 복사 없이 조작한다면 다른 경우에서 조작하기 위한 원본을 잃기 때문이다. 이를 copy_mat 함수를 사용해 쉽게 깊은 복사를 구현했다.
5. 이렇게 깊은 복사한 mat을 copyed_mat으로 두었는데, 이 2차원 배열에서 가장 긴 연속길이를 구하는 함수를 calc_longest 함수로 두었으며, 이 함수 내부에서는 2차원 배열의 가로세로 각각의 라인의 최대 연속 길이를 구하는 calc_length 함수를 사용해 최대 길이를 계산했다.
6. 이 과정에서 최대길이가 N인 경우라면 더이상 진행해도 N을 넘길 수 없기 때문에 N을 반환한다.

결과

맞았습니다!!