[백준][파이썬] 3085번 사탕 게임

 3085번 : 사탕 게임

문제

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

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

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

입력

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

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

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

출력

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

링크

3085번: 사탕 게임 (acmicpc.net)

3085번: 사탕 게임

 

 접근 방법

1. 인접한 것끼리 (붙어있는 것끼리, 상하좌우) 원소 바꾸기
   1. 열 기준 → 현재 위치한 원소와 오른쪽 원소를 바꾸기
   2. 행 기준 → 현재 위치한 원소와 아래쪽 원소를 바꾸기
2. 바꿨을 때 먹을 수 있는 사탕의 최대 개수 확인하기
   
   1. 열 기준 → 현재 원소가 왼쪽 원소와 같으면 최대 개수 1 증가
   2. 행 기준 → 현재 원소가 위쪽 원소와 같으면 최대 개수 1 증가
   3. 열과 행에서 각각 최대 개수를 구하고 max 함수로 비교하여 더 큰 값 선택
3. 처음 상태로 되돌리기
4. 1~3을 모든 행, 열에서 진행하여 경우의 수를 확인하기 (brute force)
5. 가장 큰 값을 가지는 사탕의 개수 출력하기 

완전 탐색 참고 자료 : [알고리즘][파이썬] Exhaustive Search / 완전 탐색 — y-seo의 딩코 기록들 (tistory.com)

[알고리즘][파이썬] Exhaustive Search / 완전 탐색

 

 풀이

사실.. 특별하게 새롭게 찾아본 함수나.. 스킬은 없고

모든 경우의 수를 따지는 문제이다 보니 이중 for문을 잘 쓰고 if/else문을 잘 쓰는 데에 공을 들였다

 

 

 전체 코드

import sys
input = sys.stdin.readline

def check(board): # 사탕 최대 개수 체크
    count_max = 1
    for i in range(size):
        temp_max = 1
        for j in range(1, size): # 열 체크
            if board[i][j] == board[i][j-1]: # 연속일 때
                temp_max += 1
            else:
                temp_max = 1
            count_max = max(count_max, temp_max)
        temp_max = 1
        for j in range(1, size): # 행 체크
            if board[j][i] == board[j-1][i]: # 연속일 때
                temp_max += 1
            else:
                temp_max = 1
            count_max = max(count_max, temp_max)
    return count_max
3
size = int(input())
board = [list(input()) for i in range(size)] # 2차원 배열 
count = 0

for i in range(size):
    for j in range(size): # 완전 탐색 (brute force)
        if j+1 < size: # 열 체크
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j] # 인접한 두 문자 바꾸기
            temp = check(board)
            count = max(count, temp) # 최대 개수 체크
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j] # 돌려놓기 
        if i+1 < size: # 행 체크
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j] # 인접한 두 문자 바꾸기
            temp = check(board)
            count = max(count, temp) # 최대 개수 체크
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j] # 돌려놓기
print(count)