[Python] 사탕 게임 - 백준 (완전탐색)

해당 글은 백준 3085번 문제 '사탕 게임'을 다룬다.

문제

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

3085번: 사탕 게임

 

설명

해당 문제는 사탕의 색이 다른 인접한 두 칸을 모두 바꿔가며 완전 탐색하는 문제이다.

탐색을 진행해보면서 행과 열 중 같은 색이 가장 큰 갯수를 구해나간다.

 

코드

n = int(input())
board = []
for i in range(n):
    board.append(list(input()))

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def search(board):
    row_max, col_max = 0, 0
    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
                row_max = max(row_count, row_max)
            else:
                row_count = 1
            if board[j][i] == board[j+1][i]:
                col_count += 1
                col_max = max(col_count, col_max)
            else:
                col_count = 1
    return max(row_max, col_max)

result = 0
for i in range(n):
    for j in range(n):
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if board[i][j] != board[nx][ny]:
                board[i][j], board[nx][ny] = board[nx][ny],  board[i][j]
                result = max(result, search(board))
                board[i][j], board[nx][ny] = board[nx][ny], board[i][j]
print(result)