[백준 3085번] 사탕 게임

📝 Comment

• 백준 link: https://www.acmicpc.net/problem/3085
• Brute Force, 완전탐색 문제 + 구현
• 사탕의 색이 다른 인접한 두 칸을 확인할 때, 아래와 오른쪽만 확인하면 됨.
• 상근이가 먹을 수 있는 사탕의 최대 개수는 N개임. N개를 이미 찾았다면 그 즉시 종료 (시간복잡도 감소)

💡 유용하게 쓰일 Python

1. itertools의 groupby

• 문자열 속 연속된 문자 부분 찾을 때 사용함
• 본 문제에서는 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분 (행 또는 열) 개수 셀 때 사용

from itertools import groupby

def findContLetter(s):
    for letter, contLetter in groupby(s):
        print(letter, list(contLetter))

2. 2차원 행/열 바꾸기

list(zip(*board))

👩🏻‍💻 직접 푼 Solution

코드 모듈화 하지 않은 버전

from itertools import groupby
import sys

def findContLetter(s, N):
    result = 1
    for letter, contLetter in groupby(s):
        # print(letter, list(contLetter))
        cur_size = len(list(contLetter))
        if result < cur_size:
            result = cur_size
            if result == N:
                break
    return result

input = sys.stdin.readline

# 입력
N = int(input())
board = []
for _ in range(N):
    board.append(list(input().strip()))

answer = 1

# r: 0~N-1, c: 0~N-1을 조회 
for r in range(N):
    for c in range(N-1):
        # 하,우를 대상으로 다른 색깔일 경우 바꿀 수 있음
        down = (r+1, c)
        right = (r, c+1)
        
        # 바꿨다면? 해당 case를 완전탐색 시작 
        # 바꾸지 않았다면 완전탐색 조건 시작 못 함. 1개라도 교환해야지 탐색이 시작될 수 있음

        #print(f'board[{r}][{c}]: {board[r][c]}')
        #print(f'DOWN) board[{r+1}][{c}]: {board[down[0]][down[1]]}')
        #print(f'RIGHT) board[{r}][{c}]: {board[right[0]][right[1]]}\n')

        if down[0]<N and board[r][c] != board[down[0]][down[1]]:
            # board 바꾸기
            board[r][c], board[down[0]][down[1]] = board[down[0]][down[1]], board[r][c]

            # 모든 행/열 탐색하기
            for i in range(N):
                cur_row_answer = findContLetter(''.join(board[i]), N)
                if cur_row_answer >= N:
                    print(N)
                    exit()
                elif cur_row_answer > answer:
                    answer = cur_row_answer
            
            trap_board = list(zip(*board))
            for i in range(N):
                cur_col_answer = findContLetter(''.join(trap_board[i]), N)
                if cur_col_answer >= N:
                    print(N)
                    exit()
                elif cur_col_answer > answer:
                    answer = cur_col_answer

            # 원상태로 돌려 놓기
            board[r][c], board[down[0]][down[1]] = board[down[0]][down[1]], board[r][c]
        
        if board[r][c] != board[right[0]][right[1]]:
            # board 바꾸기
            board[r][c], board[right[0]][right[1]] = board[right[0]][right[1]], board[r][c]

            # 모든 행/열 탐색하기
            for i in range(N):
                cur_row_answer = findContLetter(''.join(board[i]), N)
                if cur_row_answer >= N:
                    print(N)
                    exit()
                elif cur_row_answer > answer:
                    answer = cur_row_answer
            
            trap_board = list(zip(*board))
            for i in range(N):
                cur_col_answer = findContLetter(''.join(trap_board[i]), N)
                if cur_col_answer >= N:
                    print(N)
                    exit()
                elif cur_col_answer > answer:
                    answer = cur_col_answer

            # 원상태로 돌려 놓기
            board[r][c], board[right[0]][right[1]] = board[right[0]][right[1]], board[r][c]
    
        # 탐색해서 모두 같은색으로 이루어진 연속 부분의 길이
        # 만약 현재 answer보다 길다면 update / N이면 break

print(answer)