[Python] 백준 3085번 - '사탕 게임' 풀이

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

3085번: 사탕 게임

---

코드

import sys
ans = 0
def check_horizontal():
    global ans
    for i in range(N):
        cnt = 1
        for j in range(1, N):
            if board[i][j] == board[i][j-1]:
                cnt += 1
            else:
                cnt = 1

            if cnt > ans:
                ans = cnt
def check_vertical():
    global ans
    for i in range(N):
        cnt = 1
        for j in range(1, N):
            if board[j][i] == board[j-1][i]:
                cnt += 1
            else:
                cnt = 1
            if cnt > ans:
                ans = cnt

N = int(sys.stdin.readline().rstrip())
board = [list(sys.stdin.readline().rstrip()) for _ in range(N)]

for i in range(N):
    for j in range(1, N):
        board[i][j], board[i][j-1] = board[i][j-1], board[i][j]
        check_vertical()
        check_horizontal()
        board[i][j], board[i][j-1] = board[i][j-1], board[i][j]

for i in range(N):
    for j in range(1, N):
        board[j][i], board[j-1][i] = board[j-1][i], board[j][i]
        check_vertical()
        check_horizontal()
        board[j][i], board[j-1][i] = board[j-1][i], board[j][i]

print(ans)

check_horiziontal 함수는 오른쪽으로 확인하고, check_vertical 함수는 아래로 확인합니다. 상하좌우 모두 확인할 필요없이 오른쪽과 아래만 바꿔가면서 확인하면 되는 문제였습니다.

 

cnt는 사탕 한개를 의미하고, 만약 같은 색깔이 있는 것이 체크된다면 한개씩 늘려 ans에 넣습니다. 다르다면 다시 1개로 돌아가야 합니다.

---

후기

진짜... 진짜 브루트했던 문제였습니다. 브루트포스 알고리즘은 편식해왔는데 억지로 먹어보니까 이런 식의 알고리즘도 해봐야 하지 않을까 라는 생각이 듭니다... 하지만 역시 편식하고 싶은..........