백준 3085번. 사탕 게임 (Python / 파이썬)

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

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

---

문제 풀이 

사탕 게임은 사탕의 색이 다른 인접한 두 칸에

들어있는 사탕을 서로 교환했을 때

모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을

골라 사탕의 최대 개수를 구하는 문제 입니다.

 

문제를 해결하기 위해 

1. 사탕의 색이 다른 인접한 두 칸의 사탕을 교환

2. 교환 후 행/열을 탐색해 사탕의 최대 개수 계산

위와 같이 두 가지 단계가 필요합니다.

 

먼저, 1번을 해결하기 위해서는 사탕의 상, 하, 좌, 우를 탐색하고

색이 다르다면 교환하도록 해주어야 합니다.

그런데 만약 사탕을 상, 하, 좌, 우로 교환해주면 그 다음 사탕은

이미 왼쪽, 위 방향은 확인이 완료된 상태입니다.

따라서 사탕의 오른쪽, 아래만 확인하여 교환해주면 됩니다. 

교환한 뒤 2번으로 넘어가 최대 개수를 계산해주면 됩니다.

최대 개수를 계산을 완료했다면 사탕의 위치를 다시 원상복구 해줍니다.

 

2번을 해결하기 위해서는 행과 열로 나누어 탐색해주어야 합니다.

먼저 행마다 연속된 사탕이 있다면 그 수를 count해주었고

만약 다른 색의 사탕이 나왔다면 count를 초기화해주었습니다.

이때, 주의할 점은 count를 해줄때마다 max값을 구해줘야한다는 것입니다.

만약 PPPCC 일 때, 처음 count 값은 3이고 그 다음 

다른 색이 나왔으므로 count가 1이 되고 최종적으로 2가 됩니다.

만약 모든 과정이 종료되고 max값을 구하면 2로 비교가 될 것입니다.

따라서 처음 count 값을 max 값으로 비교하기 위해 매 순간마다 max 값을 구해줘야 합니다. 

열에서도 위와 같이 똑같은 과정으로 사탕의 최대값을 구해줍니다.

 

위와 같은 과정을 모두 반복하면 상근이가 먹을 수 있는

사탕의 최대 개수를 구할 수 있습니다.

---

My Code

# 사탕의 최대 개수를 계산
def count_candy():
  max_count = 0
  # 행 탐색
  for i in range(n):
    count = 1 # 다음 행으로 넘어갈 때 초기화
    for j in range(n - 1):
      if board[i][j] == board[i][j + 1]: # 같은 색이라면
        count += 1 # count 증가
      else: # 다른 색이라면
        count = 1 # count 초기화
      max_count = max(max_count, count) # 최대 개수 계산
  
  # 열 탐색
  for j in range(n):
    count = 1 # 다음 열로 넘어갈 때 초기화
    for i in range(n - 1):
      if board[i][j] == board[i + 1][j]: # 같은 색이라면
        count += 1 # count 증가
      else: # 다른 색이라면
        count = 1 # count 초기화
      max_count = max(max_count, count) # 최대 개수 계산    
  return max_count

n = int(input()) # 보드의 크기

board = []
for _ in range(n):
  board.append(list(input())) # 사탕의 색상 정보

max_value = 0 # 사탕의 최대 개수를 저장할 변수
for i in range(n):
  for j in range(n):
    # 사탕의 오른쪽 탐색
    if j < n - 1 and board[i][j] != board[i][j + 1]: # 서로 다른 색이면
      board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j] # 교환
      max_value = max(max_value, count_candy())  # 교환 후 사탕의 최대 개수 구함
      board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j] # 원상복구
    # 사탕의 아래 탐색
    if i < n - 1 and board[i][j] != board[i + 1][j]: # 서로 다른 색이면
      board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j] # 교환
      max_value = max(max_value, count_candy())  # 교환 후 사탕의 최대 개수 구함
      board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j] # 원상복구

print(max_value)