[백준] 3085번 사탕 게임 (python)

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

인접한 두 사탕의 색깔이 다르면 스왑한 뒤 전체 사탕의 색깔을 탐색하면서 하나의 색으로 일치하는 가장 긴 행 or 열을 찾으면 된다. 처음에 스왑하고 유지되는 줄 알았는데, 탐색 후에 다시 원래 상태로 되돌려놔야 한다.

- 상하좌우로 탐색
- 어? 나랑 붙어있는데 색깔이 다르네?
- 스왑 후 N x N 탐색하면서 색깔이 연속하는 가장 긴 행 or 열을 찾기
- 탐색 끝나면 다시 재스왑 (원래대로 돌려놓기)
- 다시 색깔 다른 인접한 칸 찾기
- 반복

 

 

1. origin에 기존 색깔을 저장해 두고, 인접한 사탕의 색깔이 다르면 스왑 해준 뒤에 탐색하고 다시 원래대로 돌려놓는다. 이때 max_eat으로 최댓값을 갱신한다.

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

max_eat = 0
for i in range(n):
    for j in range(n):
        origin = board[i][j]

        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]

            if 0 <= nx < n and 0 <= ny < n:
                if origin != board[nx][ny]:
                    board[i][j], board[nx][ny] = board[nx][ny], origin
                    max_eat = max(max_eat, check_eat())
                    board[nx][ny], board[i][j] = board[i][j], origin

 

2. 먼저 열을 탐색해 준다. 하나의 열에 연속되는 사탕이 몇 개까지 있는지 확인한다. 만약 연속이 끊기면 0으로 초기화한다. C, P, Z, Y 중 연속되는 숫자가 가장 큰 색깔을 can_eat으로 갱신한다.

can_eat = 0

    for i in range(n):
        c_count, p_count, z_count, y_count = 0, 0, 0, 0

        for j in range(n):
            if board[i][j] == 'C':
                c_count += 1
                p_count, z_count, y_count = 0, 0, 0
            elif board[i][j] == 'P':
                p_count += 1
                c_count, z_count, y_count = 0, 0, 0
            elif board[i][j] == 'Z':
                z_count += 1
                c_count, p_count, y_count = 0, 0, 0
            else:
                y_count += 1
                c_count, z_count, p_count = 0, 0, 0

            can_eat = max(can_eat, c_count, p_count, z_count, y_count)

 

3. 다음으로 행을 탐색해 준다. 행 역시 연속되는 사탕이 몇 개까지 있는지 확인한다. 만약 연속이 끊기면 0으로 초기화한다. C, P, Z, Y 중 연속되는 숫자가 가장 큰 색깔을 can_eat으로 갱신한다.

for i in range(n):
        c_count, p_count, z_count, y_count = 0, 0, 0, 0

        for j in range(n):
            if board[j][i] == 'C':
                c_count += 1
                p_count, z_count, y_count = 0, 0, 0
            elif board[j][i] == 'P':
                p_count += 1
                c_count, z_count, y_count = 0, 0, 0
            elif board[j][i] == 'Z':
                z_count += 1
                c_count, p_count, y_count = 0, 0, 0
            else:
                y_count += 1
                c_count, z_count, p_count = 0, 0, 0
        
            can_eat = max(can_eat, c_count, p_count, z_count, y_count)
    
    return can_eat

 

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
board = [list(input().strip()) for _ in range(n)]

def check_eat():
    can_eat = 0

    for i in range(n):
        c_count, p_count, z_count, y_count = 0, 0, 0, 0

        for j in range(n):
            if board[i][j] == 'C':
                c_count += 1
                p_count, z_count, y_count = 0, 0, 0
            elif board[i][j] == 'P':
                p_count += 1
                c_count, z_count, y_count = 0, 0, 0
            elif board[i][j] == 'Z':
                z_count += 1
                c_count, p_count, y_count = 0, 0, 0
            else:
                y_count += 1
                c_count, z_count, p_count = 0, 0, 0

            can_eat = max(can_eat, c_count, p_count, z_count, y_count)

    for i in range(n):
        c_count, p_count, z_count, y_count = 0, 0, 0, 0

        for j in range(n):
            if board[j][i] == 'C':
                c_count += 1
                p_count, z_count, y_count = 0, 0, 0
            elif board[j][i] == 'P':
                p_count += 1
                c_count, z_count, y_count = 0, 0, 0
            elif board[j][i] == 'Z':
                z_count += 1
                c_count, p_count, y_count = 0, 0, 0
            else:
                y_count += 1
                c_count, z_count, p_count = 0, 0, 0
        
            can_eat = max(can_eat, c_count, p_count, z_count, y_count)
    
    return can_eat

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

max_eat = 0
for i in range(n):
    for j in range(n):
        origin = board[i][j]

        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]

            if 0 <= nx < n and 0 <= ny < n:
                if origin != board[nx][ny]:
                    board[i][j], board[nx][ny] = board[nx][ny], origin
                    max_eat = max(max_eat, check_eat())
                    board[nx][ny], board[i][j] = board[i][j], origin

print(max_eat)