[코테] 백준 브루트포스 3085번 문제

3085번 : 사탕 게임

문제 링크

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

문제 설명

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

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

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

입력

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

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

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

출력

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

문제풀이

반복하면서 행과 열을 바꾸면서 연속되는 사탕의 최대개수를 출력한다.

말로 하면 간단한건데 구현하기까지가 조금 번거로웠다.. 간소화된 코드를 짤수 있게 앞으로도 노력하자

import copy
import sys
input = sys.stdin.readline

# 행끼리 바꾸는 함수
def row_change(arr: list, row: int, col: int) -> list:
    dp = copy.deepcopy(arr)
    size = len(arr)

    if row + 1 < size : 
        dp[row], dp[row+1] = dp[row][:col] + dp[row+1][col], dp[row+1][:col] + dp[row][col]
        if col + 1 < size : 
            dp[row], dp[row+1] = dp[row] + arr[row][col+1:], dp[row+1] + arr[row+1][col+1:]
    return dp

# 열끼리 바꾸는 함수
def col_change(arr: list, row: int, col: int) -> list:
    dp = copy.deepcopy(arr)
    size = len(arr)

    if col + 1 < size :
        dp[row] = dp[row][:col] + dp[row][col+1] + dp[row][col]
        if col + 2 < size :
            dp[row] = dp[row] + arr[row][col+2:]
    return dp

# 모든 행, 열을 순회하며 연속되는 사탕이 최대인 개수를 출력
def count_candies(arr: list) -> int:
    result = 1
    size = len(arr)
    
    for i in range(size) :
        row_prev = 'None'
        col_prev = 'None'
        col_count = 1
        row_count = 1
        
        for j in range(size) :
            if col_prev == arr[i][j] :
                col_count += 1                
            else :
                result = max(result, col_count)
                col_count = 1
                col_prev = arr[i][j]

            if row_prev == arr[j][i] :
                row_count += 1
            else : 
                result = max(result, row_count)
                row_count = 1
                row_prev = arr[j][i]
        else :
            result = max(result, col_count, row_count) 

    return result


N = int(input())
arr = []

for _ in range(N):
    arr.append(input())

result = count_candies(arr)

if result == N :
    print(result)
else :
    for i in range(N):
        for j in range(N):
            result = max(result, count_candies(row_change(arr, i, j)), count_candies(col_change(arr, i, j)))
    print(result)