문제

' 3085번 사탕게임 '
https://www.acmicpc.net/problem/3085

풀이

조건

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

풀이 순서

• N, 사탕배열을 입력값으로 받는다.
• 모든 배열을 순회하면서 가로로 인접한 두 칸을 교환한 뒤, 변한 배열의 최댓값을 찾는 함수에 적용한다. 이후 배열을 원래대로 돌려놓는다.
• 세로로 인접한 두 칸을 교환한뒤, 변한 배열의 최댓값을 찾는 함수에 적용한다. 이후 배열을 원래대로 돌려놓는다.
• 구한 최댓값중에 가장 큰값을 출력한다.

Check point

• 어떤 특정 조건에만 인접한 두 칸을 바꾼다고 가정한다면 너무 복잡하게 된다. 따라서 배열의 인접한 두칸을 바꾸는 모든 경우의 사탕의 개수를 구하고 최댓값을 뽑아내는게 핵심이다.
• 2중 리스트 배열을 원본에 영향을 끼치지 않게 복사하고 싶다면 깊은복사를 써도 되지만 가장 간단한 방법은 함수를 끝내면 원래대로 돌리는 법이다.
• range 범위를 잘 고려해야 한다.

코드

Python

def find(arr):
    mx = 1
    tmp = 1
    for i in range(N):
        for j in range(N-1):  
        	#가로
            if arr[i][j] == arr[i][j+1]: # 연속한지 확인 
                tmp += 1
            else:
                tmp = 1  # tmp 초기화
            if tmp > mx:
                mx = tmp
        tmp = 1  # tmp 초기화
        #세로
        for j in range(N-1):  
            if arr[j][i] == arr[j+1][i]: # 연속한지 확인 
                tmp += 1
            else:
                tmp = 1  # tmp 초기화
            if tmp > mx:
                mx = tmp
        tmp = 1 # tmp 초기화
    return mx

N = int(input())
arr = [[] for _ in range(N)]
for i in range(N):
    a = input()
    for j in range(N):
        arr[i].append(a[j])
mx = 0
for i in range(N):
    for j in range(N):
        if j + 1 < N:
            # 가로줄  바꾸기
            arr[i][j], arr[i][j + 1] = arr[i][j + 1], arr[i][j]
            tmp = find(arr)  # 바꾼 배열의 최대값 구하기
            if tmp > mx:
                mx = tmp
            # 되돌리기
            arr[i][j], arr[i][j + 1] = arr[i][j + 1], arr[i][j]
        if i + 1 < N:
            # 세로줄 바꾸기
            arr[i][j], arr[i + 1][j] = arr[i + 1][j], arr[i][j]
            tmp2 = find(arr)
            if tmp2 > mx:
                mx = tmp2
            # 되돌리기
            arr[i][j], arr[i + 1][j] = arr[i + 1][j], arr[i][j]
print(mx)

다른 방법

def count(lst):
    cnt = ans = 1
    for i in range(1, len(lst)):
        if lst[i]==lst[i-1]:
            cnt+=1
            ans = max(ans, cnt)
        else:
            cnt=1
    return ans

def solve(arr):
    mx = 0
    for i in range(N-1):
        for j in range(0,N):
            # 오른쪽 사탕과 교환
            arr[i][j],arr[i][j+1]=arr[i][j+1],arr[i][j]
            mx = max(mx, count(arr[i]))
            arr[i][j],arr[i][j+1]=arr[i][j+1],arr[i][j]

            # 아래쪽 사탕과 교환
            arr[i][j],arr[i+1][j]=arr[i+1][j],arr[i][j]
            mx = max(mx, count(arr[i]),count(arr[i+1]))
            arr[i][j],arr[i+1][j]=arr[i+1][j],arr[i][j]
    return mx

N = int(input())
arr = [list(input())+[0] for _ in range(N)]+[[0]*(N+1)]
arr_t = list(map(list, zip(*arr)))
ans = max(solve(arr), solve(arr_t))
print(ans)