[백준 3085] 사탕 게임

문제

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

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

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

입력

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

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

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

출력

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

---

풀이

N*N 크기의 판에 4가지의 각기다른 색상의 사탕들을 채워넣고 사탕들을 상하좌우로 움직였을 때 가장 긴 행 또는 열을 구하는 문제이다. 

한번쯤은 해봤을법한 캔티팡같은 게임을 연상해보았고 결국 모든 위치의 사탕들을 한번 이상씩 옮겨봐야겠다는 생각을 했다. 마침 N의 범위도 최대 50이기에 완전탐색을 해도 시간초과가 뜰 것 같지는 않았다

먼저 N*N개의 사탕을 모두 움직여봐야하는데, 각 위치의 사탕은 상하좌우로 움직일 수 있다. 모두 상하좌우로 움직여볼수도 있겠지만 (0,0)을 우측과 교환 == (0,1)을 좌측과 교환 이기에 교환은 우측과 아랫쪽으로만 완전탐색이 된다.

여기까지의 시간 복잡도는 O(2*n**2)

# 두 원소 자리바꾸기
def Change_seat(r,c,isrow):
    if isrow:
        tmp = A[r][c]
        A[r][c] = A[r][c+1]
        A[r][c+1] = tmp
    else:
        tmp = A[r][c]
        A[r][c] = A[r+1][c]
        A[r+1][c] = tmp

# 오른쪽,아래쪽 방향으로 원소 교환 O(n**2)
for k in range(N):
    for r in range(N-1):
        Change_seat(k,r,True)
        res = Count_max(res)
        Change_seat(k,r,True)
    for c in range(N-1):
        Change_seat(c,k,False)
        res = Count_max(res)
        Change_seat(c,k,False)

 

옮긴 후에는 가장 긴 연속 부분을 판단해줘야 한다. 이 또한 각 행과 열을 모두 훑어야하므로 O(n**2)가 나온다

# 가로, 세로로 같은 색 최대 개수 카운트
def Count_max(res):
    for i in range(N):
        count_r = 1 # 가로 최대 저장
        count_c = 1 # 세로 최대 저장
        for j in range(1,N):
            if A[i][j] == A[i][j-1]: # 해당 행의 연속 계산
                count_r += 1
                if res < count_r: # 최대 길이 저장
                    res = count_r
            else:
                count_r = 1
            if A[j][i] == A[j-1][i]: # 해당 열의 연속 계산
                count_c += 1
                if res < count_c: # 최대 길이 저장
                    res = count_c
            else:
                count_c = 1
    return res

 

결과적으로 시간복잡도는 O(n**4)정도가 나오는데, n의 최댓값 50을 대입해봐도 1억은 넘지 않으니 시간 초과는 뜨지 않을 것이다