[Python] 백준 온라인 저지 3085번

실버 4 https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

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

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다.

그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

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

 

 

힌트: 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

 

 

 

[Python]

 

풀이 방법:

 

다 해보면 되는 문제, 브루트포스 예제이다.

 

테이블 크기가 50보다 작기 때문에 시간복잡도가 O(N^4)이지만 시간초과가 나지 않는다.

인접한 두 칸을 고르고 사탕을 교환하는 방법은 상하좌우로 4가지가 있다

그러나 테이블을 순차적으로 검사했을때 위로 바꾸는 방법과, 왼쪽으로 바꾸는 방법은 이전에 검사했었으므로 다시 고려할 필요가 없다.

따라서 밑으로 바꾸는 방법과 오른쪽으로 바꾸는 방법 두 가지만 고려하면 된다.

 

 

코드:

import time
import sys
sys.stdin = open("input.txt", "r")
# input = sys.stdin.readline
start_time = time.time()

# source code

def check(arr): # check는 arr 에서 인접한 것과 바꿨을 때 가장 긴 연속 부분을 찾는 함수
    n = len(arr)
    answer = 1

    for i in range(n): # 열 순회하면서 연속되는 숫자 세기
        cnt = 1
        for j in range(1, n):
            if arr[i][j] == arr[i][j-1]: # 이전 것과 같다면 cnt + 1
                cnt += 1
            else: # 다르다면 1로 초기화
                cnt = 1

            if cnt > answer: # 비교해서 현재 cnt가 더 크다면 answer 갱신
                answer = cnt

        # 이제 행 차례. 행 순회하면서 연속 숫자 세기
        cnt = 1
        for j in range(1, n):
            if arr[j][i] == arr[j-1][i]: # 이전 것과 같다면 cnt + 1
                cnt += 1
            else:
                cnt += 1
            if cnt > answer:
                answer = cnt
        return answer


n = int(input())
arr = [list(input()) for _ in range(n)]
answer = 0

for i in range(n):
    for j in range(n):
        # 열 바꾸기
        if j+1 < n:
            # 인접한 것과 바꾸기
            arr[i][j], arr[i][j+1] = arr[i][j+1], arr[i][j]
            temp = check(arr)

            if temp > answer:
                answer = temp
            # 바꿨던 것을 다시 원래대로 돌려놓기
            arr[i][j], arr[i][j+1] = arr[i][j+1], arr[i][j]

        # 행 바꾸기
        if i+1 < n:
            # 인접한 것과 바꾸기
            arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]
            temp = check(arr)
            # 바꿨던 것을 다시 원래대로 돌려놓기
            arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]

print(answer)


#

end_time = time.time()
print("WorkingTime: {} sec".format(end_time-start_time))

 

 

 

 

추가 예정 - [Javascript]

풀이 방법:

정답: