[백준/브루트포스] 3085 사탕게임(Python, 파이썬)

www.acmicpc.net/problem/3085  

3085번: 사탕 게임

 

처음에는 이 문제를 어떻게 풀어야할지 감이 안잡혔는데, 그냥 다 해보면 되는 거였다! 😀

그 이유는 테이블 크기가 50보다 작기 때문이다. 밑에 코드는 시간복잡도가 $O(N^4)$지만 애초에 테이블 크기가 작기 때문에 시간 초과가 나지 않는다.

 

인접한 두 칸을 고르고 사탕을 교환하는 방법은 상하좌우로 4가지가 있다. 

그러나 테이블을 순차적으로 검사했을때, 위로 바꾸는 방법과, 왼쪽으로 바꾸는 방법은 이전에 검사했었으므로 다시 고려할 필요가 없다.

그러므로 밑으로 바꾸는 방법과, 오른쪽으로 바꾸는 방법 두 가지만 고려하면 된다.

 

 

import sys
input=sys.stdin.readline

def check(arr):
    n=len(arr)
    answer=1

    for i in range(n):
        # 열 순회하면서 연속되는 숫자 세기
        cnt=1
        for j in range(1, n):
            if arr[i][j] == arr[i][j-1]:
        	# 이전 것과 같다면 cnt에 1 더하기
                cnt += 1
            else:
            # 이전과 다르다면 다시 1로 초기화
                cnt=1
                
            # 비교해서 현재 cnt가 더 크다면 answer 갱신하기
            if cnt > answer:
                answer = cnt

        # 행 순회하면서 연속되는 숫자 세기
        cnt=1
        for j in range(1, n):
            if arr[j][i] == arr[j-1][i]:
        	# 이전 것과 같다면 cnt에 1 더하기
                cnt += 1
            else:
            # 이전과 다르다면 다시 1로 초기화
                cnt=1
                
            # 비교해서 현재 cnt가 더 크다면 answer 갱신하기
            if cnt > answer:
                answer = cnt

    return answer

n=int(input())
arr=[list(input()) for _ in range(n)]
answer=0

for i in range(n):
    for j in range(n):
        # 열 바꾸기
        if j+1 < n:
        	# 인점한 것과 바꾸기
            arr[i][j], arr[i][j+1] = arr[i][j+1], arr[i][j]
            
            # check는 arrd에서 인점한 것과 바꿨을 때 가장 긴 연속한 부분을 찾아내는 함수이다
            temp=check(arr)

            if temp > answer:
                answer = temp
               
            # 바꿨던 것을 다시 원래대로 돌려놓기
            arr[i][j], arr[i][j+1] = arr[i][j+1], arr[i][j]

        # 행 바꾸기
        if i+1 < n:
        	# 인점한 것과 바꾸기
            arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]
            
            # check는 arrd에서 인점한 것과 바꿨을 때 가장 긴 연속한 부분을 찾아내는 함수이다
            temp=check(arr)

            if temp > answer:
                answer = temp
            
            # 바꿨던 것을 다시 원래대로 돌려놓기
            arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]
            
print(answer)