백준 문제 중 3085번, 브루트포스, ‘브루트포스’

백준 문제 중 3085번

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

문제

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

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

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

입력

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

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

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

출력

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

---

풀이

입력이 3<=n<=50으로 제한되어 있고, 비교적 작을 수 이므로 단순하게 하나씩 비교해 나가면 된다.

from typing import List

n = int(input())

 # 사탕의 상태를 입력 받을 배열 선언
candy = [None]*n

for i in range(n):

     # 각 사탕의 색을 하나씩 쪼개서 List[str]형태로 저장
    candy[i] = list(input())

 # 사탕을 먹을 수 있을때 최댓값을 세는 함수 선언
def eat(candy:List[str], cnt:int)->int:

    for i in range(n):

        tmp1,tmp2 =1,1

        for j in range(n-1):
    
             # 좌우로 인접한 사탕의 종류가 같다면 먹을 수 있고 
             # 카운트를 위해 같다면 1을 계속 더해줌
            if candy[i][j]==candy[i][j+1]:

                tmp1+=1

             # 만약 다른 종류가 나온다면 1로 초기화
            else:

                tmp1=1

             # 상하로 인접한 사탕의 종류가 같다면 먹을 수 있고
             # 카운트를 위해 같다면 1을 계속 더해줌
            if candy[j][i]==candy[j+1][i]:

                tmp2+=1

            else:

                tmp2=1

             # 입력받은 cnt와 tmp1,tmp2중 최대를 cnt에 저장
            cnt = max(cnt,tmp1,tmp2)
 
    return cnt



cnt,cnt1,cnt2=0,0,0

for i in range(n):

    for j in range(n-1):

         # 좌우 종류가 다른경우 서로 바꾸고 eat함수를 호출,
         # eat 함수로 cnt1를 계산한뒤 다시 원래 상태로 되돌림
        if candy[i][j]!=candy[i][j+1]:

            candy[i][j], candy[i][j+1] = candy[i][j+1], candy[i][j]

            cnt1 = eat(candy,cnt)

            candy[i][j], candy[i][j+1] = candy[i][j+1], candy[i][j]

         # 상하 종류가 다른경우 서로 바꾸고 eat함수를 호출,
         # eat 함수로 cnt2를 계산한뒤 다시 원래 상태도 되돌림
        if candy[j][i]!=candy[j+1][i]:

            candy[j][i], candy[j+1][i] = candy[j+1][i], candy[j][i]

            cnt2 = eat(candy,cnt)

            candy[j][i], candy[j+1][i] = candy[j+1][i], candy[j][i]

        cnt = max(cnt1,cnt2)

print(cnt)

3
ZCY
ZCP
PYZ
[['C', 'Z', 'Y'], ['Z', 'C', 'P'], ['P', 'Y', 'Z']]
[['Z', 'Y', 'C'], ['Z', 'C', 'P'], ['P', 'Y', 'Z']]
[['Z', 'C', 'Y'], ['P', 'C', 'P'], ['Z', 'Y', 'Z']]
[['Z', 'C', 'Y'], ['C', 'Z', 'P'], ['P', 'Y', 'Z']]
[['Z', 'C', 'Y'], ['Z', 'P', 'C'], ['P', 'Y', 'Z']]
[['Z', 'C', 'Y'], ['Z', 'Y', 'P'], ['P', 'C', 'Z']]
[['Z', 'C', 'Y'], ['Z', 'C', 'P'], ['Y', 'P', 'Z']]
[['Z', 'C', 'P'], ['Z', 'C', 'Y'], ['P', 'Y', 'Z']]
[['Z', 'C', 'Y'], ['Z', 'C', 'P'], ['P', 'Z', 'Y']]
[['Z', 'C', 'Y'], ['Z', 'C', 'Z'], ['P', 'Y', 'P']]
2