백준 boj 3085 - 사탕 게임 (파이썬, python)

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

3085번: 사탕 게임

 

브루트포스를 활용하여 문제를 해결하였다.

 

문제 제한 시간이 1초라 시간초과에 유의했으나,

애초에 입력값이 작아 o(n^4) 되는 나의 솔루션도 문제가 없는 것 같다.

 

풀이는 입력값을 받은 배열에 있는 모든 원소를

가로로 한 번 교체하여 최대값을 확인하고,

세로로 한 번 교체하여 최대값을 확인하였다.

다만 교체한 후에는 원상복귀하여 배열에 이상이 없게 해야했다. 

그렇게 도출된 cnt와 result를 비교하여 더 큰 값을 결과값으로 도출하였다.

 

파이썬의 스왑은 언제나 감동적이다...

 

code

 

n = int(input())
result = 0
bombo = [list(input()) for _ in range(n)]

def check_bombo():
    global result
    for i in range(n): # 가로 맥스 카운팅
        cnt = 1
        for j in range(n - 1):
            if bombo[i][j] == bombo[i][j + 1]:
                cnt += 1
                result = max(result, cnt)
            else:
                cnt = 1

    for i in range(n): # 세로 맥스 카운팅
        cnt = 1
        for j in range(n - 1):
            if bombo[j][i] == bombo[j + 1][i]:
                cnt += 1
                result = max(result, cnt)
            else:
                cnt = 1

for i in range(n):
    for j in range(n - 1):
            bombo[i][j], bombo[i][j + 1] = bombo[i][j + 1], bombo[i][j] # 가로 교체
            check_bombo()
            bombo[i][j + 1], bombo[i][j] = bombo[i][j], bombo[i][j + 1] # 원복

            bombo[j][i], bombo[j + 1][i] = bombo[j + 1][i], bombo[j][i] # 세로 교체
            check_bombo()
            bombo[j + 1][i], bombo[j][i] = bombo[j][i], bombo[j + 1][i] # 원복
print(result)