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

문제

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

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

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

입력

• 첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
• 다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다.
• 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
• 사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

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

예제

입력1

3
CCP
CCP
PPC

출력1

3

입력2

4
PPPP
CYZY
CCPY
PPCC

출력2

4

입력3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

출력3

4

풀이

풀이에 앞서, 조금 주먹구구식으로 풀었는데 통과가 되었다. 함수를 만들며 풀고 이리저리 고치면 더 보기 좋은 코드가 나올수 있으나, 이 코드는 그렇지 않음.

import sys

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

N = int(input())
matrix = [list(input()) for _ in range(N)]	# 문자열로 받은것을 리스트로 변환하여 저장
rst = 0						# 먹을 수 있는 사탕 최대 개수

for x in range(N):				# 행
    for y in range(N):				# 열
    
        # 움직이지 않은 상태에서 사탕 최대 개수.
        std = matrix[x][y]			# 원 상태의 x행 y열 사탕 색상.

        # 열 탐색. 탐색할 때에는 좌측과 우측 또는 상단과 하단을 각각 확인.
        # 좌,우측에서 끝까지 가거나 현재 색상과 같지 않은 것이 나올때까지 카운트
        cnt = 1
        lt, rt = y - 1, y + 1
        while lt >= 0 and matrix[x][lt] == std:	# 현재 위치 기준 좌측
            cnt += 1
            lt -= 1
        while rt < N and matrix[x][rt] == std:	# 현재 위치 기준 우측
            cnt += 1
            rt += 1
        rst = max(rst, cnt)

        # 행 탐색
        cnt = 1
        lt, rt = x - 1, x + 1
        while lt >= 0 and matrix[lt][y] == std:	# 현재 위치 기준 상단
            cnt += 1
            lt -= 1
        while rt < N and matrix[rt][y] == std:	# 현재 위치 기준 하단
            cnt += 1
            rt += 1
        rst = max(rst, cnt)

	# 현 위치 기준 상, 우, 하, 좌 순서대로 사탕을 바꾸며 비교.
        for i in range(4):
            # 바꿀 사탕 위치
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 바꿀 사탕 위치가 유효한지 확인.
            if 0 <= nx < N and 0 <= ny < N and matrix[x][y] != matrix[nx][ny]:
                # 사탕 위치 교환
                matrix[x][y], matrix[nx][ny] = matrix[nx][ny], matrix[x][y]
                std = matrix[x][y]			# 교환 후 현재 위치 사탕 색
                
                # 열 탐색. 사탕 교환 전 확인 과정과 같다.
                cnt = 1					# 먹을 수 있는 사탕 개수
                lt, rt = y - 1, y + 1
                while lt >= 0 and matrix[x][lt] == std:
                    cnt += 1
                    lt -= 1
                while rt < N and matrix[x][rt] == std:
                    cnt += 1
                    rt += 1
                rst = max(rst, cnt)
                
                # 행 탐색
                cnt = 1
                lt, rt = x - 1, x + 1
                while lt >= 0 and matrix[lt][y] == std:
                    cnt += 1
                    lt -= 1
                while rt < N and matrix[rt][y] == std:
                    cnt += 1
                    rt += 1
                rst = max(rst, cnt)
                
                # 확인 후 교환했던 사탕 원위치.
                matrix[x][y], matrix[nx][ny] = matrix[nx][ny], matrix[x][y]

                if rst == N:	# 만약 먹을수 있는 사탕 개수가 N과 같다면 더 커질 수 없으므로
                    print(rst)	# 출력 후 종료
                    sys.exit()

print(rst)