[백준/파이썬] 3084번: 사탕게임 (Python)

문제

www.acmicpc.net/problem/3085

풀이

- 완전탐색/ 브루트 포스 알고리즘

- 열의 사탕을 swap 한 뒤, 행과 열의 사탕 최대개수를 각각 구한뒤 비교한다

- 행의 사탕을 swap 한 뒤, 행과 열의 사탕 최대개수를 각각 구한뒤 비교한다

 

코드

# 3085번. 사탕게임
# 완전탐색
# 가로 사탕 최대 개수 구하기
def checkrow(a):
    maxNum = 1
    for i in range(0,n):
        cnt = 1
        for j in range(1, n):
            if (a[i][j] == a[i][j - 1]):
                cnt += 1
                maxNum = max(maxNum, cnt)
            else:
                cnt = 1
    return maxNum
# 세로 사탕 최대 개수 구하기
def checkcol(a):
    maxNum = 1
    for j in range(0, n):
        cnt = 1
        for i in range(1, n):
            if (a[i][j] == a[i-1][j]):
                cnt += 1
                maxNum = max(maxNum, cnt)
            else:
                cnt = 1
    return maxNum

n = int(input()) # 입력

# 입력값 2차원 배열에 넣기
arr = [[0 for _ in range(n)] for _ in range(n)]
for i in range(0, n):
    a = list(input())
    for j in range(0,n):
        arr[i][j] = a[j]


arr2 = arr
result = 0
# 가로로 사탕 swap
for i in range(0,n):
    for j in range(0,n-1):
        if (arr2[i][j] != arr2[i][j + 1]):
            arr2[i][j], arr2[i][j + 1] = arr2[i][j + 1], arr2[i][j]  # swap
            a = checkrow(arr2) # 가로 사탕개수 비교
            result = a if a > result else result # max값 얻기
            a = checkcol(arr2) # 세로 사탕개수 비교
            result = a if a > result else result # max값 얻기
            arr2[i][j], arr2[i][j + 1] = arr2[i][j + 1], arr2[i][j]  # swap 원상복구

# 가로로 사탕 swap
for i in range(0,n-1):
    for j in range(0,n):
        if (arr2[i][j] != arr2[i+1][j]):
            arr2[i][j], arr2[i+1][j] = arr2[i+1][j], arr2[i][j]  # swap
            a = checkrow(arr2) # 가로 사탕개수 비교
            result = a if a > result else result # max값 얻기
            a = checkcol(arr2) # 세로 사탕개수 비교
            result = a if a > result else result # max값 얻기
            arr2[i][j], arr2[i+1][j] = arr2[i+1][j], arr2[i][j]  # swap 원상복구

print(result)