Baekjoon [3085] 사탕게임 - python

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력 1

3
CCP
CCP
PPC

예제 출력 1

3

예제 입력 2

4
PPPP
CYZY
CCPY
PPCC

예제 출력 2

4

예제 입력 3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 3

4

문제 풀이

n = int(input())

board = [list(input()) for _ in range(n)]
# print(board)

def row():
    max_cnt = 0
    for i in range(n):
        cnt = 1
        for j in range(n):
            if j >=0 and j < n-1:
                if board[i][j] == board[i][j+1]:
                    cnt +=1
                    if max_cnt < cnt:
                        max_cnt = cnt
                else:
                    cnt =1
    return max_cnt

def column():
    max_cnt = 0
    for i in range(n):
        cnt = 1
        for j in range(n):
            if j >=0 and j < n-1:
                if board[j][i] == board[j+1][i]:
                    cnt +=1
                    if max_cnt < cnt:
                        max_cnt = cnt
                else:
                    cnt =1
    return max_cnt

total_cnt = 0
for i in range(n): # 0, 1, 2
    for j in range(n-1): # 0, 1, 2
        if board[i][j] != board[i][j+1]: # row 별로 swap을 진행하여 i와 j를 비교하여 진행
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j] # swap
            row_cnt = row()
            column_cnt = column()
            if row_cnt >= column_cnt:
                if total_cnt < row_cnt:
                    total_cnt = row_cnt
            else:
                if total_cnt < column_cnt:
                    total_cnt = column_cnt
            board[i][j+1],board[i][j] = board[i][j],board[i][j+1]

        if board[j][i] != board[j+1][i]: # column 별로 swap을 진행하여 i와 j를 변경하여 진행
            board[j][i], board[j+1][i] = board[j+1][i], board[j][i] # swap
            row_cnt = row()
            column_cnt = column()
            if row_cnt >= column_cnt:
                if total_cnt < row_cnt:
                    total_cnt = row_cnt
            else:
                if total_cnt < column_cnt:
                    total_cnt = column_cnt
            board[j+1][i],board[j][i] = board[j][i],board[j+1][i]
print(total_cnt)

문제 풀이해석

풀때 약간 애를 먹었던 문제였습니다.

해당 과정을 진행해보면 기본적으로 입력값을 board로 입력하여 2차원 배열로 진행합니다. 이후 row와 column별로 인접한 값을 비교탐색을 진행합니다. 이때 비교한 값이 다르다면 이를 swap을 진행한 후에 column과 row별로 cnt를 증가시킵니다. 인접한 데이터가 있다면 값을 2로 간주하며 시작하니, 초기 cnt값을 1로 설정하여 진행합니다. 

cnt값을 증가시켜 기존 설정한 max_cnt보다 크면 이를 바꿔 진행합니다. 이후 모든 board를 다 탐색하여 최종적으로 total_cnt를 도출합니다.