(백준 알고리즘 문제풀이) 3085번 사탕게임

문제

 

문제 링크

 

문제 접근

• 사탕의 종류: C(빨간색), P(파란색), Z(초록색), Y(노란색)
• N x N 행렬에 사탕을 채워넣는다.
• 사탕의 색이 다른 인접한 두칸을 고른다.
• 고른 칸에 들어있는 사탕을 서로 교환한다.
• 가장 긴 연속적인 부분 행 또는 열을 고른 후 사탕의 최대 개수를 출력한다.

코드

 

import sys


def board_max_value(board, N):
    row_count, col_count = 1, 1
    # 행 개수 확인
    for i in range(N):
        temp = 1
        for j in range(1, N):
            if board[i][j-1] == board[i][j]:
                temp += 1
            else:
                row_count = max(row_count, temp)
                temp = 1
        row_count = max(row_count, temp)

    # 열 개수 확인
    for i in range(N):
        temp = 1
        for j in range(1, N):
            if board[j-1][i] == board[j][i]:
                temp += 1
            else:
                col_count = max(col_count, temp)
                temp = 1
        col_count = max(col_count, temp)

    return max(row_count, col_count)


# 0. N x N 행렬에 사탕을 채워넣는다.
N = int(sys.stdin.readline())
board = list([""] * N for _ in range(N))
d = [(1, 0), (-1, 0), (0, -1), (0, 1)]

for i in range(N):
    line = sys.stdin.readline().strip()
    for j in range(N):
        board[i][j] = line[j]

max_count = board_max_value(board, N)

# 1. 사탕의 색이 다른 인접한 두칸을 고른다.
for i in range(N):
    for j in range(N):
        for k in range(len(d)):
            dx = i + d[k][0]
            dy = j + d[k][1]
            # 2. 인접한 두칸을 교환하고 개수확인 후 다시 교환
            if 0 <= dx < N and 0 <= dy < N:
                if board[i][j] != board[dx][dy]:
                    board[i][j], board[dx][dy] = board[dx][dy], board[i][j]
                    max_count = max(max_count, board_max_value(board, N))
                    board[i][j], board[dx][dy] = board[dx][dy], board[i][j]

print(max_count)

느낀점

알고리즘에 대하여 생각하는 것은 간단하였지만 그것을 구현하는 데이 소요되는 시간은 오래 걸린 편이었다. 생각으로는 간단하지만 이것을 구현하는데에 대한 생각을 많이 해봐야겠다고 생각했다. 그리고 BFS와 비슷하게 생각하여 문제를 풀었는데 다양한 방법을 보면서 코드리뷰까지 마쳤다. 나만의 코드에 대하여 문제를 풀기보다는 다른 사람들의 코드를 검토하면서 코드리뷰하는 시간도 가져보아야겠다.