[백준] 3085: 사탕 게임

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

import sys
def solution():
    n = int(sys.stdin.readline())
    board = [ list(sys.stdin.readline().strip()) for _ in range(n) ]
    max_length = 1
    def max_candy_count(board, n):
        max_count = 1
        for i in range(n):
            row_count, col_count = 1, 1
            for j in range(n-1):
                if board[i][j] == board[i][j+1]: # 오른쪽 칸과 비교
                    row_count += 1
                    max_count = max(max_count, row_count)
                else:
                    row_count = 1 # 연속이 끊기면 다시 1부터 시작
                if board[j][i] == board[j+1][i]: # 아래 칸과 비교
                    col_count += 1
                    max_count = max(max_count, col_count)
                else:
                    col_count = 1 # 연속이 끊기면 다시 1부터 시작
        return max_count
    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] # 한 칸 오른쪽과 비교
            max_length = max(max_length, max_candy_count(board, n))
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j] # 원상 복구

            board[j][i], board[j+1][i] = board[j+1][i], board[j][i] # 한 칸 아래와 비교
            max_length = max(max_length, max_candy_count(board, n))
            board[j][i], board[j+1][i] = board[j+1][i], board[j][i]
    print(max_length)
solution()

한 개 칸씩(오른쪽, 아래) 교환해주며 보드의 가장 긴 연속부분을 탐색하고 탐색 후 원상 복구 하는 과정을 반복해서 실행하는 풀이법입니다. j를 반복할 때는 리스트 에러가 발생하지 않도록 n-1까지 반복해야 하고, 오른쪽 비교 시에는 board[i][j+1], 아래 칸과 비교 시에는 board[j+1][i]로 작성합니다.