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

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

3085번: 사탕 게임

 

문제

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

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

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

 

입력

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

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

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

 

출력

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

 

 

---

풀이

35분정도 걸렸다. 대부분 구현하는데 시간이 들었다.

문제 조건에서 N이 50 이하라고 지정해주기도 했고, 완전탐색 이외의 방법이 생각나지도 않아서 완전탐색으로 풀었다.

 

사탕 배열을 전부 돌며 아래쪽 혹은 왼쪽에 연속되지 않은 사탕의 조합이 있다면 스왑하고 countMax함수로 연속되는 같은 색의 최대 사탕 수를 셌다.

 

연속되는 사탕이 가로로 있을 수도, 세로로 있을 수도 있어서 두 방향 모두 체크해야한다.

처음엔 numpy의 전치행렬 기능을 써서 countMax를 재사용했었는데, 제출해보니 ModuleNotFoundError가 떴다..

백준에서 넘파이 못쓰는지 처음 알았다. 프로그래머스에서는 됐었는데 ㅜ

 

아무튼 그래서 countMaxTranspose함수를 새로 만들어 체크했다. 시간은 이 편이 덜 들긴 할 것 같다.

import sys
input = sys.stdin.readline

n = int(input())
candy = [list(input())[:-1] for _ in range(n)]

def countMax(arr):
    maxcnt = 1
    for i in range(n):
        cnt = 1
        c = arr[i][0]
        for j in range(1, n):
            if arr[i][j] == c:
                cnt += 1
                maxcnt = max(maxcnt, cnt)
            else:
                c = arr[i][j]
                cnt = 1
    return maxcnt

def countMaxTranspose(arr):
    maxcnt = 1
    for i in range(n):
        cnt = 1
        c = arr[0][i]
        for j in range(1, n):
            if arr[j][i] == c:
                cnt += 1
                maxcnt = max(maxcnt, cnt)
            else:
                c = arr[j][i]
                cnt = 1
    return maxcnt

answer = 0
for i in range(n):
    for j in range(n):
        if j != 0 and candy[i][j-1] != candy[i][j]: #가로로 스왑
            candy[i][j-1], candy[i][j] = candy[i][j], candy[i][j-1]
            answer = max(answer, countMax(candy), countMaxTranspose(candy))
            candy[i][j - 1], candy[i][j] = candy[i][j], candy[i][j - 1]
        if i != n-1 and candy[i][j] != candy[i+1][j]: #세로로 스왑
            candy[i][j], candy[i+1][j] = candy[i+1][j], candy[i][j]
            answer = max(answer, countMax(candy), countMaxTranspose(candy))
            candy[i][j], candy[i+1][j] = candy[i+1][j], candy[i][j]
print(answer)

통과!