문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1

3
CCP
CCP
PPC

예제 출력 1

3

예제 입력 2

4
PPPP
CYZY
CCPY
PPCC

예제 출력 2

4

예제 입력 3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 3

4

나의 코드

from sys import stdin as s
# 오늘 나를 구제해 준 라이브러리 itertools
import itertools

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n = int(s.readline().strip())

board = []

for i in range(n):
    board.append(list(map(str, s.readline().strip())))

# get_max_candies가 각 행에서의 최대 candy수만 구해주므로 board를 90도로 돌려서 한 번 더 호출하기 위해 만든 함수
def rotate_board(board):
    new_board = []
    for i in range(n):
        row = []
        for j in range(n - 1, -1, -1):
            row.append(board[j][i])
        new_board.append(row)
    return new_board


result = 0

# board를 인자로 받아서 itertools를 사용하여 각 행에서의 최대 candy 수를 구함.
def get_max_candies(board):
    # 각 행에 대해서 
    for row in board:
        max_value_each_row = 0
        # 
        for _, group in itertools.groupby(row):
            max_value_each_row = max(max_value_each_row, len(list(group)))

        global result
        if max_value_each_row > result:
            result = max_value_each_row


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def solution(x, y):
    # 상하좌우 탐색
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if nx < 0 or ny < 0 or nx >= n or ny >= n:
            continue
        if board[nx][ny] == board[x][y]:
            continue
     # 2개의 candy를 swap
        board[nx][ny], board[x][y] = board[x][y], board[nx][ny]
        # candy가 swap되었을 때 각 행에서의 최대 candy 수를 구함.
        get_max_candies(board)
        # candy가 swap되었을 때 각 열에서의 최대 candy 수를 구함.
        get_max_candies(rotate_board(board))
        # 탐색을 종료하면 다시 원상 복귀 시킴.
        board[nx][ny], board[x][y] = board[x][y], board[nx][ny]

# 하나의 좌표씩 solution 함수의 인자로 전달
for i in range(n):
    for j in range(n):
        solution(i, j)

print(result)

와 통과~!~!
2차원 배열을 완전탐색하여 풀 수 있는 문제이다.
나 이거 어떻게 풀었지?!!!!!!! 내가 풀고나서도 신기하군 ㅋㅋㅋㅋㅋㅋㅋ
구현 유형이 계속 너무 자신이 없었는데 풀고 나니까 감격 스럽다 흑ㅎ긓극

어떻게 풀었냐면.. 진정하고 리뷰합시다..

2차원 배열의 좌표 인덱스를 solution 함수에 인자로 하나씩 전달하고, 각각의 인덱스에서 swap할만한 candy가 있는지 찾고, 만약 있다면 get_max_candies 함수를 호출하여 최대 candy 빙고의 크기를 구하는 것이다.
내가 만든 get_max_candies의 함수는 각 행에서의 최대 candy 빙고만 구할 수 있게 만들어놓았는데, 그럼 board의 각 열에서의 최대 candy는 어떻게 구하나욥?!! board를 90도 회전하는 함수를 만들어서 그 결과 배열을 인자로 하여 get_max_candies를 한번 더 호출하였다.

완전탐색 유형이기 때문에 탐색 종료 시 swap했던 candy를 다시 되돌려주어야 한다. 탐색하면서 계속 갱신해온 최대값을 마지막에 반환하면 끝!

이 문제에서 제일 어려웠던 부분은 get_max_candies 함수 내부에서 빙고의 크기를 구하는 것이었다. 그런데 파이썬 라이브러리인 itertools의 groupby 함수를 이용하면 배열에서 최대 빙고 크기를 아주 쉽게 구할 수 있었다.
아름답구나.. itertools..

유용한 itertools 라이브러리를 앞으로도 적재적소에 활용하기 위해 다시 짚고 넘어가자.

❤️ itertools 라이브러리는 사랑입니다. ❤️

 for _, group in itertools.groupby(row):
            max_value_each_row = max(max_value_each_row, len(list(group)))

itertools.groupby 함수는 iterable을 받아 연속된 동일한 원소들을 그룹화하는 이터레이터를 반환한다. 각 그룹은 원래 (key, group) 형태의 tuple로 표현된다. key는 그룹의 공통값이다. 반면 이 문제에서는 key가 필요하지 않기 때문에 _로 표시하였다.

[활용 예시]

array = [3, 3, 3, 5, 5, 6, 8, 9, 9, 9, 1, 1, 3, 3, 3, 4, 5]
for key, group in itertools.groupby(array):
    print(key)
    print(list(group))
    
# 3
# [3, 3, 3]
# 5
# [5, 5]
# 6
# [6]
# 8
# [8]
# 9
# [9, 9, 9]
# 1
# [1, 1]
# 3
# [3, 3, 3]
# 4
# [4]
# 5
# [5]

이코테로 공부하고 새롭게 풀 줄 알게된 영역들이 늘어난 게 느껴진다. 앞으로 더 열심히 하자~~~ 이제 리액트 공부하러 슝쓩!!