백준-사탕 게임(3085, 파이썬)

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

3085번: 사탕 게임

 

문제이해

• NxN 크기에 사탕을 채워 놓는데 사탕의 색은 모두 같지 않을 수도 있다.
• 상근이는 사탕의 색이 다른 인접한 두 칸을 고르고 고른 칸에 들어있는 사탕을 서로 교환한다.
• 모두 같은 색으로 이뤄져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕들을 먹는다.
• 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하자.

문제풀이

• 사탕은 한번만 교환이 가능한 것 같다. => 문제에 추가되어야할 조건
• 상,하,좌,우를 모두 살피고 색이 다른 사탕이 존재한다면 교환하자.
• 교체를 하고 입력받은 사탕들의 열과 행에 있는 연속된 사탕 수를 체크한다.
• 연속된 사탕 수 체크는 주어진 사탕색으로 문자열을 생성하고 이 값이 매개변수로 전달된 문자열에 존재하는지 확인하는 방식으로 진행하였다.

풀이코드

n=int(input())
candy=[list(input()) for _ in range(n)]
ans=1

def check(check_str):
    global ans
    global n
    alpha=['C', 'P', 'Z', 'Y']

    for a in alpha:
        for num in range(1, n+1):
            if num>ans and a*num in check_str:
                ans=max(num, ans)

def solution(candy, px, py, n):
    dx=[1, 0]
    dy=[0, 1]

    for x, y in zip(dx, dy):
        nx=px+x
        ny=py+y
        if 0<=nx<n and 0<=ny<n and candy[px][py]!=candy[nx][ny]:
            candy[px][py], candy[nx][ny]=candy[nx][ny], candy[px][py]
            for i in range(n):
                check(''.join(candy[i]))
                check(''.join(c[i] for c in candy))
            candy[px][py], candy[nx][ny]=candy[nx][ny], candy[px][py]
# 교체하지 않았을 때의 체크
for i in range(n):
    check(''.join(candy[i]))
    check(''.join([c[i] for c in candy]))

for i in range(n):
    for j in range(n):
        solution(candy, i, j, n)
print(ans)

처음에는 교체한 행 또는 열에 대해서만 체크를 했는데 이경우 80퍼센트에서 틀렸습니다가 나왔다.

내가 생각했을 때 한번 교체하는 것이 하나의 경우이기 때문에 위 같은 경우가 반례인 것 같다.