[BOJ] 사탕 게임

---

코드

import sys
input = sys.stdin.readline

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

def calcMaxCandy():
    ret = 0
    # 가장 긴 부분행 계산
    for i in range(n):
        subret = 1
        for j in range(n):
            if j == 0: 
                prev = board[i][j]
                continue

            if prev == board[i][j]:
                subret += 1
                if subret > ret: ret = subret
            else:
                subret = 1
                prev = board[i][j]

    # 가장 긴 부분열 계산
    for i in range(n):
        subret = 1
        for j in range(n):
            if j == 0: 
                prev = board[j][i]
                continue

            if prev == board[j][i]:
                subret += 1
                if subret > ret: ret = subret
            else:
                subret = 1
                prev = board[j][i]
            
    return ret

# 가로로 교환 후 계산
for i in range(n):
    for j in range(n-1):
        board[i][j], board[i][j+1] = board[i][j+1], board[i][j]    # 교환
        val = calcMaxCandy()
        if val > ans: 
            ans = val
        board[i][j], board[i][j+1] = board[i][j+1], board[i][j]    # 원래대로
        

# 세로로 교환 후 계산
for i in range(n-1):
    for j in range(n):
        board[i][j], board[i+1][j] = board[i+1][j], board[i][j]    # 교환
        val = calcMaxCandy()
        if val > ans: 
            ans = val
        board[i][j], board[i+1][j] = board[i+1][j], board[i][j]    # 원래대로

print(ans)

결과

풀이 방법

• n의 크기가 최대 50이기 때문에 특별한 알고리즘을 사용하지 않고 완전탐색으로 구현만 잘 하면 해결되었다.
• 모든 n x n개 문자에 대해 가로, 세로로 인접한 문자와 서로 교환 후 문제에서 원하는 가장 긴 부분행/열 길이를 계산해보고 최대값을 갱신하는 방식으로 구현했다.

---