[백준/Python] 3085번: 사탕 게임

문제

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

3085번: 사탕 게임

---

문제 요약

N X N 크기의 보드에 여러 종류의 사탕을 채워 놓는다.

 

사탕의 색이 다른 인접한 두 칸을 고르고 서로 자리를 교환한다.

 

모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고르고 그 사탕을 모두 먹는다.

 

먹을 수 있는 사탕의 최대 개수를 출력한다.

 

< 색 표현 >

빨간색: C

파란색: P

초록색: Z

노란색: Y

---

코드

def check(): # 배열 arr의 가장 긴 연속 부분의 길이를 찾는 함수
    global res

    # 가로 방향 연속된 부분의 최대 길이 구하기
    for i in range(N):
        cnt = 1 # 원소 한 개는 길이 1
        for j in range(1, N):
            if arr[i][j] == arr[i][j - 1]: # 왼쪽에 있는 원소와 값이 같다면 
                cnt += 1 # 증가
            else: # 왼쪽에 있는 원소와 값이 다르면
                res = max(res, cnt) # 현재 개수를 res와 비교하여 갱신
                cnt = 1 # 연속된 부분의 길이를 1로 다시 초기화
        
        res = max(res, cnt) # 한 행의 탐색이 종료되면 res를 갱신

    # 세로 방향 연속된 부분의 최대 길이 구하기
    for j in range(N):
        cnt = 1
        for i in range(1, N):
            if arr[i][j] == arr[i - 1][j]: # 위에 있는 원소와 값이 같다면 
                cnt += 1
            else: # 위에 있는 원소와 값이 다르면
                res = max(res, cnt)
                cnt = 1

        res = max(res, cnt)

N = int(input())

arr = [list(input()) for _ in range(N)]

res = 1 # 최대 길이

# 가로 방향 원소 교체
for i in range(N):
    for j in range(N - 1):
        arr[i][j], arr[i][j + 1] = arr[i][j + 1], arr[i][j] # 원소 교체
        check()
        arr[i][j], arr[i][j + 1] = arr[i][j + 1], arr[i][j] # 원소 복귀 (다시 교체)

for i in range(N - 1):
    for j in range(N):
        arr[i][j], arr[i + 1][j] = arr[i + 1][j], arr[i][j] # 원소 교체
        check()
        arr[i][j], arr[i + 1][j] = arr[i + 1][j], arr[i][j] # 원소 복귀 (다시 교체)

print(res)

---

코드 설명

1 -1. 입력 받은 2차원 배열 arr에서 오른쪽에 인접한 원소와 교환할 원소를 반복문을 통해 하나씩 접근하고 교체한다.

 

1 - 2. 교체된 배열 arr에서 가장 긴 연속 부분의 길이를 찾으며 res를 갱신한다.

+ res의 초기값은 1이다. (arr에서 연속한 부분이 없는 경우)

 

1 - 3. 교체된 배열 arr에서 전에 교체한 원소 둘을 다시 교체하여 원래의 배열 arr로 복구한다.

 

2 - 1. 아래쪽에 인접한 원소와 교환할 원소를 반복문을 통해 하나씩 접근하고 교체한다.

 

2 - 2. 교체된 배열 arr에서 가장 긴 연속 부분의 길이를 찾으며 res를 갱신한다.

 

2 - 3. 교체된 배열 arr에서 전에 교체한 원소 둘을 다시 교체하여 원래의 배열 arr로 복구한다.

 

3. res를 출력한다.