[백준 3085번] 사탕 게임

n = int(input())

array = [[] for _ in range(n)]

nx = [-1,1,0,0]
ny = [0,0,-1,1]

for i in range(n):
    array[i] = list(input())

# 행에서 연속된 문자의 개수를 확인하는 함수
def row_check(x,y):
    count = 1
    for i in range(y,n+1):
        if i == n-1:
            break
        if array[x][i] == array[x][i+1]:
            count += 1
        else:
            break

    for i in range(y,-1,-1):
        if i == 0:
            break
        if array[x][i] == array[x][i-1]:
            count += 1
        else:
            break
    return count

# 열에서 연속된 문자의 개수를 확인하는 함수
def col_check(x,y):
    count = 1
    for i in range(x,n+1):
        if i == n-1:
            break
        if array[i][y] == array[i+1][y]:
            count += 1
        else:
            break
    for i in range(x,-1,-1):
        if i == 0:
            break
        if array[i][y] == array[i-1][y]:
            count += 1
        else:
            break
    return count

max_value = 0

for i in range(n):
    for j in range(n):
        copy_array = array

        if max(row_check(i,j), col_check(i,j)) > max_value:
            max_value = max(row_check(i,j), col_check(i,j))
        
        for k in range(4):
            temp_x = i + nx[k]
            temp_y = j + ny[k]

            if temp_x >=0 and temp_x < n and temp_y >=0 and temp_y < n:

                copy_array[i][j], copy_array[temp_x][temp_y] = copy_array[temp_x][temp_y], copy_array[i][j]
                
                if max(row_check(i,j), col_check(i,j)) > max_value:
                    max_value = max(row_check(i,j), col_check(i,j))

                copy_array[i][j], copy_array[temp_x][temp_y] = copy_array[temp_x][temp_y], copy_array[i][j]
print(max_value)

이번 문제는 각 자리에서 인접한 칸(상-하-좌-우)과 사탕을 교환하여 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 or 열)의 길이를 구하는 문제이다.

 

먼저 '행에서 연속 부분을 구하는 함수(row_check)'와 '열에서 연속 부분을 구하는 함수(col_check)'를 구현하였다.

 

그 후 해당 자리에서의 경우의 수와, 상하좌우로 사탕을 교환하였을 때의 경우의 수의 최대 값을 구하여 최대 사탕 개수(max_value)를 갱신시켜주는 방식으로 해결하였다.

 

BruteForce 알고리즘을 이해해볼 수 있었던 좋은 문제였다.