[Python 파이썬] 백준 3085번 - 사탕 게임

2024년 7월 12일

문제 링크 :백준 3085번 - 사탕 게임

문제

 

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

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

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

입력

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

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

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

출력

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

 

 

알고리즘 분류

• 구현
• 브루트포스 알고리즘

---

 

문제 접근

 

우리가 해야하는 작업은 다음과 같다.

 

1. 각 행의 인접한 열을 서로 바꾸고 모든 보드의 요소들에 대해 연속되는 사탕이 최대 몇 개인지 파악하기

2. 각 열의 인접한 행을 서로 바꾸고 모든 보드 의 요소들에 대해 연속되는 사탕이 최대 몇 개인지 파악하기

 

안타깝지만 정말 무식하게 해야한다. 단순 구현 문제이니 만큼 문제가 어떤걸 요구하고 있고 어떤 작업을 순차적으로 진행해야 하는지 분석하고 코드를 작성해야 한다.

 

# 1. 각 행의 인접한 열을 서로 바꾸기

for row in range(N):
    for col in range(N - 1):
        board[row][col], board[row][col + 1] = board[row][col + 1], board[row][col]
        
        # 모든 보드의 요소를 순회하며 연속되는 사탕이 최대 몇 개인지 파악하기
        findMaxCandy()
        
        # 보드 원상태로 되돌리기
        board[row][col], board[row][col + 1] = board[row][col + 1], board[row][col]

 

# 2. 각 열의 인접한 행을 서로 바꾸기
for col in range(N):
    for row in range(N - 1):
        board[row][col], board[row + 1][col] = board[row + 1][col], board[row][col]
        
        # 모든 보드의 요소를 순회하며 연속되는 사탕이 최대 몇 개인지 파악하기
        findMaxCandy()
        
        # 모드 원상태로 되돌리기
        board[row][col], board[row + 1][col] = board[row + 1][col], board[row][col]

 

위 두 작업은 보드를 다시 되돌리는 작업이 무조건 추가로 진행되어야 한다.

매 경우 인접한 행 혹은 열을 한 번만 스왑해준다는 조건이기 때문이다.

 

 

# 보드를 순회하며 연속되는 사탕이 최대 몇 개인지 파악하기
def findMaxCandy():
    global maxCnt

    # 행 탐색
    for row in range(N):
        nowCnt = 0
        nowColor = ""
        for col in range(N):
            if nowColor != board[row][col]:
                maxCnt = max(maxCnt, nowCnt)
                nowCnt = 1
                nowColor = board[row][col]
            else:
                nowCnt += 1
        maxCnt = max(maxCnt, nowCnt)

    # 열 탐색
    for col in range(N):
        nowCnt = 0
        nowColor = ""
        for row in range(N):
            if nowColor != board[row][col]:
                maxCnt = max(maxCnt, nowCnt)
                nowCnt = 1
                nowColor = board[row][col]
            else:
                nowCnt += 1
        maxCnt = max(maxCnt, nowCnt)

 

스왑이 진행된 보드에 대해 각 행에서 연속되는 사탕의 개수와, 각 열에서 연속되는 사탕의 개수를 계속 비교한다.

 

연속된다의 기준은 이전 색을 담고 있는 nowColor와 현재 탐색하는 보드의 요소가 같은 색일 때를 의미한다.

---

입력 예제

 

3
CCP
CCP
PPC

 

 

 

출력 예제

 

3

 

 

---

전체 코드

 

# 3085
def findMaxCandy():
    global maxCnt

    # 행 탐색
    for row in range(N):
        nowCnt = 0
        nowColor = ""
        for col in range(N):
            if nowColor != board[row][col]:
                maxCnt = max(maxCnt, nowCnt)
                nowCnt = 1
                nowColor = board[row][col]
            else:
                nowCnt += 1
        maxCnt = max(maxCnt, nowCnt)

    # 열 탐색
    for col in range(N):
        nowCnt = 0
        nowColor = ""
        for row in range(N):
            if nowColor != board[row][col]:
                maxCnt = max(maxCnt, nowCnt)
                nowCnt = 1
                nowColor = board[row][col]
            else:
                nowCnt += 1
        maxCnt = max(maxCnt, nowCnt)

if __name__ == "__main__":
    N = int(input())

    board = []
    for _ in range(N):
        board.append(list(input()))

    maxCnt = 0
    findMaxCandy()

    for row in range(N):
        for col in range(N - 1):
            board[row][col], board[row][col + 1] = board[row][col + 1], board[row][col]
            findMaxCandy()
            board[row][col], board[row][col + 1] = board[row][col + 1], board[row][col]

    for col in range(N):
        for row in range(N - 1):
            board[row][col], board[row + 1][col] = board[row + 1][col], board[row][col]
            findMaxCandy()
            board[row][col], board[row + 1][col] = board[row + 1][col], board[row][col]

    print(maxCnt)

 

 

---

풀이 후기

 

단순 구현 문제는 문제가 요구하는 바를 명확히 이해하고 순서도를 생각한 후, 코드를 작성하는 것이 문제를 빠르게 풀 수 있는 방법 중 하나라고 생각한다.