[백준/3085] 사탕 게임 (Python)

Problem : https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

Difficulty : Silver 2

 

Status : Solved

 

Time : 00:10:33

 

---

 

문제 설명

 

 

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

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

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

 

 

입력 및 출력

 

입력

 

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

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

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

 

출력

 

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

 

입력 예시

 

3
CCP
CCP
PPC

 

출력 예시

 

3

 

 

---

 

풀이

 

임의의 두 위치를 변환하는 경우의 수는 2*N*(N-1)개이며, 전체를 탐색하며 먹을 수 있는 사탕의 개수 역시 2*N*(N-1)이다. 또한 N은 최대 50이므로,  모든 경우의 수를 전부 제한시간내에 테스트하는 게 가능하다. 따라서 브루트포스 접근을 시도해 볼 수 있겠다.

 

풀이 코드

import sys
input = sys.stdin.readline
N = int(input())
map_list = [list(input().strip()) for _ in range(N)]

def check_longest() :
  result = 1
  for i in range(N) :
    rtarget, rcnt = map_list[i][0], 1
    wtarget, wcnt = map_list[0][i], 1 
    for j in range(1, N) :
      if rtarget == map_list[i][j] :
        rcnt += 1
      else :
        result = max(result, rcnt)
        rtarget, rcnt = map_list[i][j], 1
      if wtarget == map_list[j][i] :
        wcnt += 1
      else :
        result = max(result, wcnt)
        wtarget, wcnt = map_list[j][i], 1
    result = max(result, rcnt, wcnt)
  return result

answer = 0
for i in range(N) :
  for j in range(N-1) :
    map_list[i][j], map_list[i][j+1] = map_list[i][j+1], map_list[i][j]
    answer = max(answer, check_longest())
    map_list[i][j], map_list[i][j+1] = map_list[i][j+1], map_list[i][j]
    map_list[j][i], map_list[j+1][i] = map_list[j+1][i], map_list[j][i]
    answer = max(answer, check_longest())
    map_list[j][i], map_list[j+1][i] = map_list[j+1][i], map_list[j][i]
print(answer)

풀이 완료!