사탕 게임

백준 3085

• 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다.
• 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다.
• 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
• 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
• 첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
• 다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
• 사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
• 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

입출력

입력	출력
3 CCP CCP PPC	3
4 PPPP CYZY CCPY PPCC	4
5 YCPZY CYZZP CCPPP YCYZC CPPZZ	4

---

접근 방식

:

알게된 점

• 자기 자신과 오른쪽과 아래쪽을 각각 바꾼다.
  • 행 교환, 열 교환
• 교환한 후의 보드에서 또 각 행, 열에서 가장 많이 연속된 수를 카운트한다.
• 보드를 원래대로 돌려놓는다.

➡ 문제의 조건대로 '그냥 하면 된다'.

주의할 점

값 비교 시 max함수 사용했더니 시간초과.
if문으로 직접 비교할 것.

코드

import sys

n = int(sys.stdin.readline())
board = [list(sys.stdin.readline()) for _ in range(n)]

def check(board):
    ans = 1
    # 열 순회
    for i in range(n):
        cnt = 1
        for j in range(n-1):
            if board[i][j] == board[i][j+1]:
                cnt += 1
            else:
                cnt = 1
            if cnt > ans:
                ans = cnt

        # 행 순회
        cnt = 1
        for j in range(n-1):
            if board[j][i] == board[j+1][i]:
                cnt += 1
            else:
                cnt = 1
            if cnt > ans:
                ans = cnt
    return ans

answer = 0
for i in range(n):
    for j in range(n):
        # 행 바꾸기
        if i+1 < n:
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
            tmp = check(board)
            if tmp > answer:
                answer = tmp
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

        # 열 바꾸기
        if j+1 < n:
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            tmp = check(board)
            if tmp > answer:
                answer = tmp
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

print(answer)