[브루트 포스] 3085 사탕 게임

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

3085번: 사탕 게임

---

입력

if __name__ == '__main__':
    N = int(sys.stdin.readline().strip())
    candies = [list(sys.stdin.readline().strip()) for _ in range(N)]

첫째줄에 보드의 크기 N(3<=N<=50)을 정수 형태로 저장한다

N개의 줄에 문자열 형식으로 주어지는 사탕의 색상을 배열로 변환하여 저장한다

 

함수(보드의 각 위치에서 사탕을 교환하는 함수)

def solve(board):
    n = len(board)
    answer = 0
    for i in range(n):
        for j in range(n):
            # 가로 방향 교환
            if j + 1 < n:
                board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
                answer = max(answer, count_candy(board))
                board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

            # 세로 방향 교환
            if i + 1 < n:
                board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
                answer = max(answer, count_candy(board))
                board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

    return answer

2차원 배열인 board를 board[0][0]부터 순회하며 각 위치에서 가로+1, 세로+1 한번씩 사탕의 위치를 교환하며 가장 max 값을 찾는다

이때 교환하려는 좌표의 위치가 범위를 벗어나지 않도록 조건 체크를 한다

교환 이후, 다시 원래대로 돌려놓는다

 

함수(보드의 가로 및 세로 방향으로 연속된 사탕의 개수를 세는 함수)

def count_candy(board):
    n = len(board)
    max_count = 0
    for i in range(n):
        count_row = 1
        count_col = 1
        for j in range(1, n):
            # 가로 방향 확인
            if board[i][j] == board[i][j-1]:
                count_row += 1
                max_count = max(max_count, count_row)
            else:
                count_row = 1
            
            # 세로 방향 확인
            if board[j][i] == board[j-1][i]:
                count_col += 1
                max_count = max(max_count, count_col)
            else:
                count_col = 1

    return max_count

가로 방향과 세로 방향으로 순회하며 연속된 사탕의 개수를 저장한다

 

전체 코드

import sys

# 보드의 가로 및 세로 방향으로 연속된 사탕의 개수를 세는 함수
def count_candy(board):
    n = len(board)
    max_count = 0
    for i in range(n):
        count_row = 1
        count_col = 1
        for j in range(1, n):
            # 가로 방향 확인
            if board[i][j] == board[i][j-1]:
                count_row += 1
                max_count = max(max_count, count_row)
            else:
                count_row = 1
            
            # 세로 방향 확인
            if board[j][i] == board[j-1][i]:
                count_col += 1
                max_count = max(max_count, count_col)
            else:
                count_col = 1

    return max_count

# 보드의 각 위치에서 사탕을 교환한 뒤 다시 원래대로 돌려놓음
def solve(board):
    n = len(board)
    answer = 0
    for i in range(n):
        for j in range(n):
            # 가로 방향 교환
            if j + 1 < n:
                board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
                answer = max(answer, count_candy(board))
                board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

            # 세로 방향 교환
            if i + 1 < n:
                board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
                answer = max(answer, count_candy(board))
                board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

    return answer


if __name__ == '__main__':
    N = int(sys.stdin.readline().strip())
    candies = [list(sys.stdin.readline().strip()) for _ in range(N)]
    print(solve(candies))