[Python] 3085번 사탕게임

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

 

처음 알고리즘은 다음과 같이 생각했다.

행(row)에서 최대값을 갖는 알고리즘은 위와 같다. 

열(col)의 경우에는 반대로 동일하게 적용한다.

def row_cnt(b): #행
    max_cnt=1
    for i in range(0,N):
        cnt=1
        for j in range(1,N):
            if b[i][j-1]==b[i][j]: #왼쪽(좌우)값이 같다면
                cnt+=1
            elif j!=N-1:
                if b[i][j-1]==b[i][j+1]:
                    b[i][j],b[i][j+1]=b[i][j+1],b[i][j]
            else:
                cnt=1
        max_cnt=max(max_cnt,cnt)
    return max_cnt
        
def col_cnt(b): #열
    max_cnt=1
    for j in range(0,N):
        cnt=1
        for i in range(1,N):
            if b[i-1][j]==b[i][j]: #아래(상하) 값이 같다면
                cnt+=1
            elif i!=N-1:
                if b[i-1][j]==b[i+1][j]:
                    b[i][j],b[i+1][j]=b[i+1][j],b[i][j]
            else:
                cnt=1
        max_cnt=max(max_cnt,cnt)
    return max_cnt

 

하지만 이렇게 될 경우 테스트케이스1을 만족할 수 없었다. 

왜냐하면 행과 열에 대해서만 찾아가므로 행의 값을 바꾸었을 때 열에 최대 값이 있는 경우는 찾지 못했다.

 

결국,,, 그래서 답안을 보게 되었다.

# 최대 연속된 사탕 개수 계산 함수
def max_candy(board, N):
    max_count = 1  # 최소 1개의 사탕이 있음

    # 행 검사
    for i in range(N):
        count = 1
        for j in range(1, N):
            if board[i][j] == board[i][j - 1]:  # 이전 것과 같으면 증가
                count += 1
                max_count = max(max_count, count)
            else:
                count = 1  # 다르면 초기화

    # 열 검사
    for j in range(N):
        count = 1
        for i in range(1, N):
            if board[i][j] == board[i - 1][j]:  # 이전 것과 같으면 증가
                count += 1
                max_count = max(max_count, count)
            else:
                count = 1  # 다르면 초기화

    return max_count

# 메인 실행 코드
N = int(input())  # 보드 크기 N 입력
board = [list(input()) for _ in range(N)]  # 보드 입력

max_result = max_candy(board, N)  # 초기 상태에서 최대 연속 사탕 개수

# 인접한 사탕을 교환하면서 최댓값 찾기
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]
            max_result = max(max_result, max_candy(board, N))
            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]
            max_result = max(max_result, max_candy(board, N))
            board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]  # 원래대로 복구

print(max_result)

 

결과적으로 내가 생각했던 알고리즘에서 크게 벗어나지는 않았다.

다만, 내가 간과했던 점은 모든 경우를 전부 탐색하는 경우도 있다는 것이였다.
또한, 코드를 작성하면서 "이렇게 길고 복잡한 코드가 맞을까?" 하는 두려움 때문에 중간에 포기했던 것도 문제였다.

앞으로는 코드가 길든, 다소 지저분하든 끝까지 고민하며 해결하는 연습을 해야겠다.