[BOJ#3085] 사탕 게임

https://www.acmicpc.net/problem/3085

1 초

128 MB

48445

16889

11575

33.712%

문제

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

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

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

입력

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

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

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

출력

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

---

제출 코드

import sys
input = sys.stdin.readline

di = [0, 1, -1, 0]
dj = [1, 0, 0, -1]

# 바꿀때마다 일렬로 최대길이 확인하기
def check():
    global result
    # 행 확인
    for i in range(N):
        cnt = 1  # 연속되는 사탕의 수
        for j in range(1, N):
            if arr[i][j] == arr[i][j-1]:
                cnt += 1
                result = max(result, cnt)
            else:
                cnt = 1  # 연속이 끊기면 카운트를 1로 초기화

    # 열 확인
    for j in range(N):
        cnt = 1  # 연속되는 사탕의 수
        for i in range(1, N):
            if arr[i][j] == arr[i-1][j]:
                cnt += 1
                result = max(result, cnt)
            else:
                cnt = 1  # 연속이 끊기면 카운트를 1로 초기화        

# 사탕 상하좌우로 바꾸기 (다를경우에만)
def change(si, sj):
    for k in range(4):
        ni = si + di[k]
        nj = sj + dj[k]
        if 0 <= ni < N and 0 <= nj < N and arr[si][sj] != arr[ni][nj]:
            arr[si][sj], arr[ni][nj] = arr[ni][nj], arr[si][sj]
            check()
            arr[si][sj], arr[ni][nj] = arr[ni][nj], arr[si][sj]

N = int(input().strip())
arr = []
for line in range(N):
    arr.append(list(input().strip()))

result = 0
for i in range(N):
    for j in range(N):
        change(i, j)

print(result)

 

입력 갯수가 작다고 판단해서 브루트포스가 충분히 가능하다고 생각됐다.

사탕을 상하좌우로 확인해서 다르면 바꾸고 일렬로 모든 행열을 검사해주었다.

바꾸는 부분에서 (예를들어 [1][3]에서 아래로 바꿀때와 [2][3]에서 위로 바꿀때) 중복이 일어나는 부분이 있는데,

이 부분은 좀 더 고민을 해봐야할 것 같다..