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

https://www.acmicpc.net/problem/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%로 잘못되었습니다.

내가 생각할 때 한 번 교환하는 것이 하나의 경우이므로 위의 경우가 반례처럼 보입니다.