[백준] 사탕 게임 (Python)

✏️ 문제

3085번: 사탕 게임

✏️ 풀이

SWAP 할 수 있는 모든 경우의 수를 탐색해야 한다.

탐색 방향은 우측, 아래로 정하였다.

탐색 대상 원소와 우측/아래 원소와 다를 경우 SWAP하고, 배열에서 가장 긴 연속 부분의 길이를 구한다.

길이를 구한 후에는 다음 탐색을 위해 배열을 원상복구 시킨다. (다시 SWAP 해줌)

배열에서 가장 긴 연속 부분의 길이를 구할 때에는 열과 행에 대해 각각 연속된 길이일 경우 count를 증가시키고, 가장 큰 count를 구할 수 있도록 구현하였다.

✏️ 코드

size = int(input())
arr = [list(input()) for _ in range(size)]
MAX = 1

def getMaxCnt():
    global MAX
    # 가로 최대값 찾기
    for i in range(size):
        cnt = 1
        for j in range(1, size):
            if arr[i][j]==arr[i][j-1]:
                cnt += 1
                if MAX < cnt:
                    MAX = cnt
            else:
                cnt = 1

    # 세로 최대값 찾기
    for i in range(size):
        cnt = 1
        for j in range(1, size):
            if arr[j][i]==arr[j-1][i]:
                cnt += 1
                if MAX < cnt:
                    MAX = cnt
            else:
                cnt = 1


# 우측, 아래 방향으로 진행
for i in range(size):
    for j in range(size):
        # 우측 검사
        if j < size-1:
            if arr[i][j] != arr[i][j+1]:
                arr[i][j], arr[i][j+1] = arr[i][j+1], arr[i][j]  # SWAP
                getMaxCnt()
                arr[i][j], arr[i][j+1] = arr[i][j+1], arr[i][j]  # 원상복구
        # 아래 검사
        if i < size-1:
            if arr[i][j] != arr[i+1][j]:
                arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]
                getMaxCnt()
                arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]

print(MAX)