[백준] 3085. 사탕 게임

 

📪 [사탕 게임]

 

3085번: 사탕 게임

---

 

 

📋 문제설명

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

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다.

상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다.

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

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

 

 

 

👁‍🗨 입출력 데이터

[입력]

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

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다.

빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

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

3
CCP
CCP
PPC

[출력]

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

3

 

 

 

 

🔑 문제풀이

문제 이해하기

해당 문제는 모든 경우의 수를 고려해야 하는 '브루트포스 (Brute Force)', 완전탐색 문제로 다음의 두 과정을 통해 답을 도출할 수 있다.

 

1. 인접한 두 사탕을 교환한다. (단, 2번 후 원위치로 복구할 것)

2. 가장 긴 연속부분(행 또는 열)을 구한다.

 

이때 NxN으로 2차원 배열이므로 이중 for문의 0부터 n까지의 반복을 통해 교환과 탐색을 진행해야 한다. (O(N^2))

따라서 교환(1)과 탐색(2) 모두 시간복잡도 O(N^2)을 가지므로 전체 시간복잡도는 O(N^4)이다.

허나 교환 및 탐색시 상하좌우 방향을 모두 고려해야한다고 착각할 수 있지만 이는 중복의 경우를 포함하기에 '우'와 '하'의 조건으로만 해당시켜도 충분하다. 이를 이용한 해당 풀이의 코드는 아래와 같다. 

 

def search_max_candy(n, candy_l):  # 고정된 상황. 최대 캔디 수만 세기.
    count_max_row = 1
    count_max_col = 1
    for x in range(n):
        count_row = 1
        count_col = 1
        for y in range(n - 1):
            if candy_l[x][y] == candy_l[x][y + 1]:  # '우'와 동일 여부 비교.(row) (세로 마지막 열 배제)
                count_row += 1
                if count_max_row < count_row:
                    count_max_row = count_row
            else:
                count_row = 1
            if candy_l[y][x] == candy_l[y+1][x]:  # '하'와 동일 여부 비교.(col) (가로 마지막 행 배제)
                count_col += 1
                if count_max_col < count_col:
                    count_max_col = count_col
            else:
                count_col = 1
    return max(count_max_row, count_max_col)


input_n = int(input())
candy_list = [list(input()) for _ in range(input_n)]
count_ans = 0
for i in range(input_n):
    for j in range(input_n):
        # '우'와 '하'의 경우만 고려 - 인접한 사탕을 교환
        if i + 1 < input_n :  # '하'의 경우 - 행이 최대 행일 경우, '하' 교환 성립 X. 따라서 해당 경우 배제.
            candy_list[i][j], candy_list[i + 1][j] = candy_list[i + 1][j], candy_list[i][j]
            max_count = search_max_candy(input_n, candy_list)
            if max_count > count_ans:
                count_ans = max_count
            candy_list[i][j], candy_list[i + 1][j] = candy_list[i + 1][j], candy_list[i][j]
        if j + 1 < input_n :  # '우'의 경우 - 행이 최대 행일 경우, '우' 교환 성립 X. 따라서 해당 경우 배제.
            candy_list[i][j], candy_list[i][j+1] = candy_list[i][j+1], candy_list[i][j]
            max_count = search_max_candy(input_n, candy_list)
            if max_count > count_ans:
                count_ans = max_count
            candy_list[i][j], candy_list[i][j+1] = candy_list[i][j+1], candy_list[i][j]

print(count_ans)

위의 풀이의 경우 상하좌우에서 '우'와 '하'로 경우의 수를 줄였음에도 이중 for문을 두번 연속하여 콜 하므로 전체 시간 복잡도의 경우 그대로 'O(N^4)'이다. 😡

다행스럽게도 N의 범위가 50이하로 작기에, 위의 풀이로 풀어도 시간 제한에 충분하다.

허나 만약 N의 범위가 500일 경우 N의 네제곱은 1억을 넘기에 1초 제한시간에 아웃되게 된다.

그렇다면 이를 어떻게 더 효율적인 코드로 바꿀 수 있을까?

 

교환 후 탐색하는 코드를 보면, 매번 교환 이후 이중 for문을 통해 모든 NxN을 탐색하는 것을 알 수 있다. 허나, 사실 임의의 두 칸을 변경할 경우 정답에 변화가 있는 것은 최대 3개의 행과 열이기에 이는 매우 비효율적이다. 따라서 이를 고려하여 아래와 같이 풀이를 구현할 수 있다. 
// 이후 코드는 생략

 

 

 

 

 

 

 

---

 

 

 

 

🔔 풀이/개념정리

1. 이중 리스트 컴프리헨션
   : 리스트_네임= [list(input()) for _ in range(N)]
2. 파이썬 swap
   : a,b = b,a 
3. (TIP) 2차원 배열 등 배열 문제 → x(row), y(col) 변수 고정하기.