[백준] 3085 사탕 게임 python( *)

문제

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

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

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

입력

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

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

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

출력

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

코드

# 3085

import sys
n = int(sys.stdin.readline())
arr = [list(sys.stdin.readline().strip()) for _ in range(n)]
answer = 0

# 완전 탐색
def check(array):
    max_len = 1 # 함수의 리턴 값 -> 가장 긴 최대 길이
    for i in range(n):
        # 열 비교
        cnt = 1 # 같은 색인 최대 길이
        for j in range(1,n):
            if arr[i][j] == arr[i][j-1]:
                cnt += 1
            else: # 인접한 사탕 중 다른 색 나오면 cnt 초기화
                cnt = 1
            max_len = max(max_len, cnt) # max_len 갱신
        
        # 행 비교
        cnt = 1  # 같은 색인 최대 길이
        for j in range(1,n):
            if arr[j][i] == arr[j-1][i]:
                cnt += 1
            else:
                cnt = 1
            max_len = max(max_len, cnt)  # max_len 갱신
    return max_len

# 인접하고 색 다른 두 칸 고르고 완탐 호출
for i in range(n):
    for j in range(n):
        if j+1<n: # 인접한 열 끼리 비교 후 교체
            if arr[i][j] != arr[i][j+1]:
                arr[i][j],arr[i][j+1] = arr[i][j+1], arr[i][j]
                # 완전탐색 수행
                tmp = check(arr)
                # 정답과 완탐 CNT 비교
                answer = max(answer,tmp)
                # 교체 한 것 다시 원래대로 돌려놓기 ( 모든 경우의수 비교해야함)
                arr[i][j], arr[i][j + 1] = arr[i][j + 1], arr[i][j]

        if i+1<n: # 인접한 행 끼리 비교 후 교체
            if arr[i][j] != arr[i+1][j]:
                arr[i][j], arr[i + 1][j] = arr[i + 1][j],arr[i][j]
                # 완전탐색 수행
                tmp = check(arr)
                # 정답과 완탐 CNT 비교
                answer = max(answer, tmp)
                # 교체 한 것 다시 원래대로 돌려놓기 ( 모든 경우의수 비교해야함)
                arr[i][j], arr[i + 1][j] = arr[i + 1][j], arr[i][j]
print(answer)

풀이

보드의 크기 N이 주어진다. (3 ≤ N ≤ 50) -> 완전 탐색 가능하다.

 

1. 색이 다른 인접한 두 사탕 선택 후 교체

2. 교체한 배열에서 같은 사탕 색이 있는 (행 또는 열) 최대 길이 구하기

3. 교체한 사탕 다시 제자리로 위치시키고 다음 인접한 사탕 교체 후 완전탐색 반복

 

계속 교체할 사탕 2개 선택해서 자리 바꾸고 완탐으로 최대 길이 구하고 리턴 시켜서

answer 값을 max 값으로 갱신시킨다.

 

이 문제 괜찮은 것 같다.

나중에 다시 풀어보자.