[BOJ] 3085 - 사탕 게임 (🥈실버 4티어)

사용 언어: Python3

문제

사탕 게임

풀이

나의 풀이

# ✅ 맵을 90도 회전 # (행을 확인하는 방식으로) 열을 확인하기 위해
def rotate(board):
    newBoard = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            newBoard[j][N-1-i] = board[i][j]
    return newBoard

N = int(input())
board = [['CPZY'.find(x) for x in input()] for _ in range(N)]

# ✅ '연속된' 같은 사탕의 최대 개수 반환
def countMaxContiguous(row):
    mx = -1e9
    cnt = 1
    for i in range(len(row) - 1):
        if row[i] == row[i+1]:
            cnt += 1
        else:
            mx = max(mx, cnt)
            cnt = 1
    mx = max(mx, cnt)
    return mx

# ✅ 바꾼 두 원소에 의해 영향을 받는 행과 열만 체크하여 사탕의 최대 개수 반환
def getCnt(x1, y1, x2, y2, board):
    rotated_board = rotate(board)
    ans = -1e9
    if x1 == x2: # 바꾼 두 원소의 행이 같은 경우
        ans = max(ans, countMaxContiguous(board[x1]))
        ans = max(ans, countMaxContiguous(rotated_board[y1]))
        ans = max(ans, countMaxContiguous(rotated_board[y2]))
    elif y1 == y2: # 바꾼 두 원소의 열이 같은 경우
        ans = max(ans, countMaxContiguous(board[x1]))
        ans = max(ans, countMaxContiguous(board[x2]))
        ans = max(ans, countMaxContiguous(rotated_board[y1]))
    return ans

def solution(board):
    global mx
    mx = -1e9
    rotated_board = rotate(board)
    # ✅ 행 확인
    for i in range(N):
        if len(set(board[i])) == 1 or len(set(rotated_board[i])) == 1: # 모든 행(열)의 원소가 같으면 바로 N 출력
            return N
        for j in range(N - 1):
            if board[i][j] == board[i][j+1]: # 같으면 패스
                continue
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            mx = max(mx, getCnt(i, j, i, j+1, board))
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j] # 다시 돌리기

    # ✅ 열 확인 (= 🌟 90도 돌린 보드로 행 확인)
    for i in range(N):
        for j in range(N - 1):
            if rotated_board[i][j] == rotated_board[i][j+1]: # 같으면 패스
                continue
            rotated_board[i][j], rotated_board[i][j+1] = rotated_board[i][j+1], rotated_board[i][j]
            mx = max(mx, getCnt(i, j, i, j+1, rotated_board))
            rotated_board[i][j], rotated_board[i][j+1] = rotated_board[i][j+1], rotated_board[i][j] # 다시 돌리기
    return mx

print(solution(board))

• 테스트 케이스: 통과
• 제출 결과: 통과
  
• 설마 부루트포스일까 한 문제인데 정말 부루트포스였다..
• 열을 확인하기 위해서 board를 90도 회전시켜 행을 확인하면 된다!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기