백준 3085번 : 사탕 게임(python)

문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1 복사

3
CCP
CCP
PPC

예제 출력 1 복사

3

예제 입력 2 복사

4
PPPP
CYZY
CCPY
PPCC

예제 출력 2 복사

4

예제 입력 3 복사

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 3 복사

4

코드

def full(candy,n):
    global max
    cnt1,cnt2=0,0
    
    for i in range(n):
        for k in range(n):
            q,p=k,i
            while(q<n and candy[i][k]==candy[i][q]):
                cnt1+=1
                q+=1
            while(p<n and candy[i][k]==candy[p][k]):
                cnt2+=1
                p+=1
            if(max<cnt1):
                max=cnt1
            if(max<cnt2):
                max=cnt2
            cnt1,cnt2=0,0
                         
max=0    
n=int(input())
candy=[]
for i in range(n):
    candy.append(list(input()))
for i in range(n):
    for k in range(n-1):
       if(candy[i][k]!=candy[i][k+1]):
            candy[i][k],candy[i][k+1]=candy[i][k+1],candy[i][k]
            full(candy,n)
            candy[i][k],candy[i][k+1]=candy[i][k+1],candy[i][k]        
#양옆
for i in range(n-1):
    for k in range(n):
       if(candy[i][k]!=candy[i+1][k]):
            candy[i][k],candy[i+1][k]=candy[i+1][k],candy[i][k]
            full(candy,n)
            candy[i][k],candy[i+1][k]=candy[i+1][k],candy[i][k]
#위아래
print(max)

코드설명

상하좌우로 값을 한번씩 바꿔줬다 되돌려놓았다를 반복해야하는데 이때 좌와 상을 실행하면 하 우에서 한것을 한번 더하는 꼴이되기 때문에 하,우로 값을 변경해주는 경우만 생각해주어도 된다.

1. 먼저 full함수는 자신의 값과 같은 값이 오른쪽과 아래로 얼마나 많이 있는지를 세주는 함수있다.

2. 오른쪽으로 가는 반복문 하나, 아래로 가는 반복문 하나를 만들어 값을 해당값과 자신의 오른쪽 또는 아래의 값과 바꾼 후 full함수를 한번 돌리고 다시 처음상태로 돌려놔주는 코드이다. 

느낀점 및 배운점

브루트 포스는 지겨울정도의 for문의 연속이다...