[Python] 백준 3085 사탕게임

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

3085번: 사탕 게임

 

문제 해결

 $N \times N$ 행렬을 만들어야 한다.

행별로, 열별로 각각 옆에 있는 사탕의 색깔이 다르다는 조건하에 서로 바꾼다음 같은 색으로 이어진 가장 긴 행 또는 가장 긴 열을 찾는다. 찾은다음 다시 사탕의 위치를 원위치 시킨다.

위의 사고를 가지고 코드를 짜면 O($N^4$)가 나온다.... 그러나 N이 작다는 것때문에 큰 문제가 되지 않는다. brute force(부루트 포스)알고리즘으로 분리되어 있는 것 보면 가능하다는 뜻..

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
box = []
for _ in range(n):
    colors = list(str(input().rstrip()))
    box.append(colors)

max_cnt = 0

def width():
    global max_cnt

    for i in range(n):
        row_cnt = 1
        for j in range(n-1):
            if box[i][j] == box[i][j+1]: # 같은 행에서 이웃열끼리 색이 같으면
                row_cnt +=1
                max_cnt = max(max_cnt, row_cnt)
            else:
                row_cnt = 1 # 이웃열끼리 색이 달라졌으므로 초기화
    return max_cnt
def height():
    global max_cnt
    for i in range(n):
        column_cnt = 1
        for j in range(n-1):
            if box[j][i] == box[j+1][i]: # 만약 같은 열 이웃행의 색이 같다면
                column_cnt +=1
                max_cnt = max(max_cnt, column_cnt)
            else:
                column_cnt = 1
    return max_cnt

for k in range(n):
    for l in range(n-1):
        if box[k][l] != box[k][l+1]: # 사탕의 색이 다른 인접한 두 칸 고르기
            box[k][l] , box[k][l+1] = box[k][l+1], box[k][l] # 고른 칸의 사탕을 서로 교환
            width()
            height()
            box[k][l+1], box[k][l] = box[k][l], box[k][l+1] # 제자리로 다시 교환
        if box[l][k] != box[l+1][k]:
            box[l][k], box[l+1][k] = box[l+1][k], box[l][k]
            width()
            height()
            box[l+1][k], box[l][k] = box[l][k], box[l+1][k]
print(max_cnt)