[백준 #3085]: 사탕 게임(python)

백준#3085:사탕게임

import sys
input=sys.stdin.readline
index = int(input())
candy_list = [list(input()) for _ in range(index)]
def row_check(new_candy_list, row, col):
    max_count=0
    row_count=1
    col_count=1
    colPlus_count=1
    for i in range(index):
        if(i==0):
            row_before=new_candy_list[row][i]
            col_before=new_candy_list[i][col]
            colPlus_before=new_candy_list[i][col+1]
            continue

        if(row_before == new_candy_list[row][i]):
            row_count+=1
        else:
            row_count=1
        row_before=new_candy_list[row][i]
        if(max_count<row_count):
            max_count=row_count

        if(col_before == new_candy_list[i][col]):
            col_count+=1
        else:
            col_count=1
        col_before=new_candy_list[i][col]
        if(max_count<col_count):
            max_count=col_count

        if(colPlus_before == new_candy_list[i][col+1]):
            colPlus_count+=1
        else:
            colPlus_count=1
        colPlus_before=new_candy_list[i][col+1]
        if(max_count<colPlus_count):
            max_count=colPlus_count
    return max_count


def col_check(new_candy_list, row, col):
    max_count=0
    col_count=1
    row_count=1
    rowPlus_count=1
    for i in range(index):
        if(i==0):
            col_before=new_candy_list[i][col]
            row_before=new_candy_list[row][i]
            rowPlus_before=new_candy_list[row+1][i]
            continue

        if(col_before == new_candy_list[i][col]):
            col_count+=1
        else:
            col_count=1

        col_before=new_candy_list[i][col]
        if(max_count<col_count):
            max_count=col_count

        if(row_before == new_candy_list[row][i]):
            row_count+=1
        else:
            row_count=1
        row_before=new_candy_list[row][i]
        if(max_count<row_count):
            max_count=row_count

        if(rowPlus_before == new_candy_list[row+1][i]):
            rowPlus_count+=1
        else:
            rowPlus_count=1
        rowPlus_before=new_candy_list[row+1][i]
        if(max_count<rowPlus_count):
            max_count=rowPlus_count
    return max_count

song=0
for row in range(index):
    for col in range(index):
        if(col+1 < index):  #가로기준 스왑
            candy_list[row][col], candy_list[row][col+1] = candy_list[row][col+1], candy_list[row][col]
            row_count=row_check(candy_list,row,col)
            if(song < row_count):
                song=row_count
            candy_list[row][col], candy_list[row][col+1] = candy_list[row][col+1], candy_list[row][col]

        if(row+1 < index):  #세로기준 스왑
            candy_list[row][col], candy_list[row+1][col] = candy_list[row+1][col], candy_list[row][col]
            col_count=col_check(candy_list,row,col)
            if(song < col_count):
                song=col_count
            candy_list[row][col], candy_list[row+1][col] = candy_list[row+1][col], candy_list[row][col]

print(song)

해당 문제는 브루트포스 알고리즘을 활용하여 해결하였다. 모든 사탕의 위치들을 바꾸어 보고 가장 많이 연결 된 사탕의 개수를출력하면 된다. 나는 최대한 효율적으로 구현하기위해 좌우를 기준으로 위치를 바꿀 경우에는 해당 사탕들의 행에대한 검사와 각각의 사탕에 대한 열에대한 검사를하고 상하를 기준으로 위치를 바꿀경우에는 해당 사탕들의 열에 대한 검사화 각각의 사탕에 대한 행에대한 검사를 하는 하는 방식으로 구현하였다. 또한 좌우 상하를 기준으로 바꾸는 방법은 해당 사탕을 기준으로 오른쪽과 아래만 바꾸어주면 된다. 이때 범위 검사를 해주는 것이 중요하다.