[백준] 3085번: 사탕 게임

문제

백준 - 3085번: 사탕 게임

분석

보드에 사탕 색상 정보가 주어지고, 색상이 다른 두 칸을 고른 다음 그 사탕들을 교환했을 때,
같은 색으로 이루어진 가장 긴 연속 부분(행 or 열)을 구하는 문제이다.

인접한 두 칸을 고를 수 있는 경우는 2x(N-1)x(N-1)+(N-1)+(N-1)이다. (하나를 고정으로 골랐다고 했을 때 오른쪽 칸과 아래쪽 칸을 고를 수 있다. 그런데 마지막 행과 마지막 열은 하나의 선택지밖에 없다.)
그리고 각 행과 열마다 가장 긴 사탕개수를 구한다고 할 때 NxN이다.
두 칸을 고를때 마다 다른 보드가 생길 것이고 그 경우마다 모든 행과 열에서 사탕개수를 구하는 것은 비효율적이다. 고른 두 칸이 영향이 미치지 않는 곳은 사탕개수가 변하지 않을 것이기 때문이다.

따라서 사탕 개수를 구할 때 고른 두 칸의 좌표를 넘겨주어 해당 두 칸의 값이 바뀌었을 때 영향이 미칠 곳만 사탕 개수를 구한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
board = [
    list(input().rstrip())
    for _ in range(n)
]

def getCandy(x1, y1, x2, y2):
    mx_len = 0
    i, j, k = x1, 0, 1
    while j < n:
        while k < n and board[i][j] == board[i][k]:
            k += 1
        mx_len = max(mx_len, k-j)
        j = k
        k = j+1
    j, i, k = y1, 0, 1
    while i < n:
        while k < n and board[i][j] == board[k][j]:
            k += 1
        mx_len = max(mx_len, k-i)
        i = k
        k = i+1
    if x1 == x2:
        j, i, k = y2, 0, 1
        while i < n:
            while k < n and board[i][j] == board[k][j]:
                k += 1
            mx_len = max(mx_len, k-i)
            i = k
            k = i+1
    elif y1 == y2:
        i, j, k = x2, 0, 1
        while j < n:
            while k < n and board[i][j] == board[i][k]:
                k += 1
            mx_len = max(mx_len, k-j)
            j = k
            k = j+1
    return mx_len
    
mx = 0
for i in range(n):
    for j in range(n):
        if i != n-1 and j != n-1:
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            mx = max(mx, getCandy(i, j, i, j+1))
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
            mx = max(mx, getCandy(i, j, i+1, j))
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
        elif i == n-1 and j != n-1:
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            mx = max(mx, getCandy(i, j, i, j+1))
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
        elif j == n-1 and i != n-1:
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
            mx = max(mx, getCandy(i, j, i+1, j))
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
print(mx)

끝으로..

간단한 문제였지만 오류를 잡는데 시간이 좀 걸렸다.