[백준] 사탕 게임 3085번 Python
문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
! 문제 생각 !
주어진 사탕 상태에서 두 칸을 교환하여 가장 긴 연속 부분을 찾아 먹을 수 있는 사탕의 최대 개수를 구하는 문제
사탕 두 칸을 교환하는 부분을 모든 가능한 경우에 대해 검사해야하는 브루트포스 알고리즘 문제라고 생각함.
그렇다면 각각 행과 열을 검사하는 로직을 구현하고, 서로 다른 색의 사탕을 교환하여 최대 연속 부분을 찾아서 출력하면 되지 않을까라는 생각으로 접근함.
주의할 점은 사탕을 서로 교환한 다음 다시 원위치로 돌리는 작업을 고려해야함. 처음에 저 부분을 떠올리지 못해서 콘솔에 찍어보는 디버깅과정에서 지우고 쓰고를 많이 반복함. 처음에 테스트케이스는 다 맞았으나 틀렸다고 떠서 반례를 찾아서 다시 수정도 많이 함.
! 풀이 !
- 주어진 사탕 상태에서 행별로 연속한 같은 색의 사탕 개수를 구하는 함수 solve1, 열별로 연속한 같은 색의 사탕 개수를 구하는 함수 solve2를 만들었음
- 각각의 함수에서 최대 연속 부분을 찾으면서, 사탕을 교환하여 최대 연속 부분을 갱신함
- 모든 가능한 교환을 시도하면서 최대 연속 부분을 찾고, 그때의 최대 사탕 개수를 출력함
! Code !
# 사탕 게임
def solve1():
global max_cnt
for i in range(N):
cnt_1 = 1 # 최초 고른 사탕 1개
for j in range(N-1):
# 행 검사 -> 색이 같으면
if board[i][j] == board[i][j+1]:
cnt_1 += 1 # 사탕 개수 +1
# 행 검사 -> 같은 색이 아니면 1로 초기화
else:
cnt_1 = 1
max_cnt = max(max_cnt, cnt_1) # 먹을 수 있는 최대사탕개수로 업데이트
def solve2():
global max_cnt
for i in range(N):
cnt_2 = 1 # 최초 고른 사탕 1개
for j in range(N-1):
# 열 검사 -> 색이 같으면
if board[j][i] == board[j+1][i]:
cnt_2 += 1 # 사탕 개수 +1
# 열 검사 -> 같은 색이 아니면 1로 초기화
else:
cnt_2 = 1
max_cnt = max(max_cnt, cnt_2) # 먹을 수 있는 최대사탕개수로 업데이트
N = int(input())
board = []
for _ in range(N):
color = list(map(str, input()))
board.append(color)
# print(board)
max_cnt = 0
for i in range(N):
for j in range(N-1):
# 색깔 서로 다른 사탕일때 -> 행 요소 검사
if board[i][j] != board[i][j+1]:
# 서로 교환한 다음 먹을 수 있는거 찾기
board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
solve1()
solve2()
# 다시 원위치로 돌려놓기
board[i][j+1], board[i][j] = board[i][j], board[i][j+1]
# 색깔 서로 다른 사탕일때 -> 열 요소 검사
if board[j][i] != board[j+1][i]:
# 서로 교환한 다음 먹을 수 있는 거 찾기
board[j][i], board[j+1][i] = board[j+1][i], board[j][i]
solve1()
solve2()
# 다시 원위치로 돌려놓기
board[j+1][i], board[j][i] = board[j][i], board[j+1][i]
print(max_cnt)