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

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

문제

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

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

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

입력

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

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

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

출력

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

---

복기

1. 사탕을 바꾼 후에 최대 개수를 찾을때 DFS를 사용해야 하나 생각했는데 그럴 필요없이 완전탐색으로 해결을 해야 했다. check 함수에서 행 체크, 열 체크를 나눠서 각각 수행했고, for loop에서도 j를 행, 열로 각각 동작하게 했다.
2. input().split()를 습관처럼 썼는데 입력이 공백으로 들어오지 않을때는 input()만 하는게 맞다
3. 완전 탐색에서 사탕의 위치를 바꾸고 다시 원래대로 돌려놓는거 잘 외워놓자.

 

 

Solution

N = int(input())

# arr = []
# for _ in range(N):
#     arr.append(list(input().split()))
arr = [list(input()) for _ in range(N)]
max_size = 0

def check(arr):
    max_cnt = 1
    # 행을 체크
    for i in range(N):
        cnt = 1
        for j in range(1, N):
            if arr[i][j] == arr[i][j-1]:
                cnt += 1
            else:
                cnt = 1
            max_cnt = max(max_cnt, cnt)
    # 열을 체크
    for i in range(N):
        cnt = 1
        for j in range(1, N):
            if arr[j][i] == arr[j-1][i]:
                cnt += 1
            else:
                cnt = 1
            max_cnt = max(cnt, max_cnt)
    return max_cnt

max_size = 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]
            max_cnt = check(arr)
            max_size = max(max_cnt, max_size)
            #바꾼거 원래대로 
            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]
            max_cnt = check(arr)
            max_size = max(max_cnt, max_size)
            # 바꾼거 원래대로
            arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]


print(max_size)