[백준][3085] 사탕 게임

• Problem Link : https://www.acmicpc.net/problem/3085
  문제

문제

N*N 배열에 사탕의 색이 주어진다. 사탕의 색이 다른 인접한 두 칸을 서로 한 번 교환할 수 있다. 이 때 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)의 길이를 구하시오.

입력

• 첫째 줄, 보드의 크기 N이 주어진다.
• 둘째 줄, 사탕의 색상이 주어진다.

출력

• 첫째 줄, 최대 길이를 출력한다.

풀이

입력이 3부터 50이라는 굉장히 작은 숫자를 보면 브루트포스 문제임을 어느정도는 생각할 수 있다. 원래는 길이가 긴 연속부분을 찾아서 양쪽 원소를 인접한 원소들이랑 교환하면서 진행하려고 했으나 굳이 그렇게 풀지 않고 색이 다른 인접한 두 칸을 한 번씩 교환해보면서 교환할 때 마다 해당 배열에서 행 또는 열의 최대 길이를 확인하면서 진행하면 풀 수 있다.

 교환은 전체 배열에서 한 번만 가능하기 대문에 다음 진행을 할 때는 항상 전에 했던 교환을 원위치 시켜야한다.

시간 복잡도가 굉장히 높다. 모든 행과 열을 인접한 원소끼리 교환해보기 때문에 N 한번, 교환 할 때 마다 모든 행과 열을 방문하면서 최대 길이를 구하므로 $N^2$이다. 그러면 시간 복잡도가 어림잡아도 O($N^3$)이 나오는데 입력값이 조금만 커져도 시간 초과가 발생할 것이다.

입력이 작으면 항상 브루트포스임을 염두해두고 문제에 접근하자.

코드

import sys

input = sys.stdin.readline

n = int(input())

arr = []
for _ in range(n):
    arr.append(list(input().strip()))


def check(arr):
    max_cnt = 1
    for i in range(n):
        cnt_row, cnt_col = 1, 1
        for j in range(1, n):
            cnt_row = cnt_row + 1 if arr[i][j] == arr[i][j - 1] else 1
            cnt_col = cnt_col + 1 if arr[j][i] == arr[j - 1][i] else 1
            max_cnt = max(max_cnt, cnt_col, cnt_row)
    return max_cnt


ans = 1
for i in range(n):
    for j in range(1, n):
        if arr[i][j] != arr[i][j - 1]:
            arr[i][j], arr[i][j - 1] = arr[i][j - 1], arr[i][j]
            ans = max(ans, check(arr))
            arr[i][j], arr[i][j - 1] = arr[i][j - 1], arr[i][j]
        if arr[j][i] != arr[j - 1][i]:
            arr[j][i], arr[j - 1][i] = arr[j - 1][i], arr[j][i]
            ans = max(ans, check(arr))
            arr[j][i], arr[j - 1][i] = arr[j - 1][i], arr[j][i]
print(ans)