[백준/Python] #3085번 사탕 게임

 

문제 

• N x N 크기의 보드에 4가지 색의 사탕이 채워져 있음
• 인접한 서로 다른 두 사탕을 교환 후 모두 같은 색으로 이루어진 가장 긴 부분(행 또는 열)을 먹음
• 먹을 수 있는 사탕의 최대 개수는? 

 

입력

보드의 크기 N (3 ≤ N ≤ 50)
보드에 채워진 사탕(빨강: C, 파랑: P, 초록: Z, 노랑: Y)

3
CCP
CCP
PPC

 

출력

먹을 수 있는 사탕의 최대 개수

3

 

정답

import sys
input = sys.stdin.readline
from collections import Counter

# 연속 행 또는 열의 최대 길이 반환 
def check_cnt(n, target_list):
    global max_cnt
    
    for i in range(n):
        # 가로 방향 카운트
        cnt = 1
        for j in range(n-1):
            if target_list[i][j] == target_list[i][j+1]:
                cnt += 1
            else:
                if cnt > max_cnt:
                    max_cnt = cnt
                cnt = 1
        if cnt > max_cnt:
            max_cnt = cnt
            
        # 세로 방향 카운트
        cnt = 1
        for j in range(n-1):
            if target_list[j][i] == target_list[j+1][i]:
                cnt += 1
            else:
                if cnt > max_cnt:
                    max_cnt = cnt
                cnt = 1
        if cnt > max_cnt:
            max_cnt = cnt

# 모든 부분을 한번씩 교체
def change(n, board):
    # 가로 교체
    for i in range(n):
        for j in range(n-1):
            if board[i][j] != board[j+1][i]:
                board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
                check_cnt(n, board)
                board[i][j+1], board[i][j] = board[i][j], board[i][j+1]
    # 세로 교체
    for i in range(n):
        for j in range(n-1):
            if board[j][i] != board[j+1][i]:
                board[j][i], board[j+1][i] = board[j+1][i], board[j][i]
                check_cnt(n, board)
                board[j+1][i], board[j][i] = board[j][i], board[j+1][i]
            
if __name__ == "__main__":
    n = int(input())
    board = [list(input().strip()) for _ in range(n)]
    max_cnt = 0
    
    change(n, board)
    print(max_cnt)

 

해결 아이디어

• BF(완전 탐색)로 하나하나 인접한 원소를 교체 → `change()`  
• 교체한 상태에서 연속된 색의 최대 길이를 업데이트 → `check_cnt()`
• 교체한 원소 다시 원위치 → `change()`  
• 최종 max_cnt 출력