[BOJ] 3085번 - 사탕 게임

---

문제설명

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

3085번: 사탕 게임

사고과정

• 브루트 포스 유형인데, 인접한데 다른 사탕인 경우들만 추려서 DFS함수로 개수를 세려고 했다. 그런데 입력예시 정답도 맞지 않고 내 소스코드가 미궁 속으로 빠져버렸다...@@...
• 1시간 넘게도 안 풀려서 풀이를 보았는데, 풀이는 인접한 사탕이 서로 다르던 아니던 그냥 인접한 사탕은 무조건 두 개를 교환해서 최대 사탕 개수를 계산하였다. 
• 사탕 2개 위치를 교환할 때, 위치 swaping 하는 방법을 생각하지 못했다.. 예전에 정렬알고리즘에서 그렇게 연습했건만...
• 가로 또는 세로를 살펴본다고 하길래 재귀함수를 왼쪽,오른쪽,위쪽,아래쪽의 경우 개별로 선언해서 사용하려 했지만 그럴 필요가 없었다. 인접한 사탕을 탐색할 때, 아래쪽과 오른쪽만 확인하면 된다. 왜냐하면 왼쪽과 위쪽은 이미 아래쪽, 오른쪽을 거쳐오면서 중복되기 때문이다.. 이걸 캐치하지 못했다..
• 결과적으로 DFS, 재귀함수는 커녕 단순히 for loop만으로 구현이 가능했다. 아직은 내게 너무 어려운 난이도이다.. 여러 번 풀어봐야 할 듯 하다.

풀이(스스로 못 푼 풀이)

n = int(input())
array = []
for _ in range(n):
    array.append(list(input()))

answer = 0
def search():
    global answer
    # 연속 가로로 되어 있는 사탕 개수 체크
    for i in range(n):
        count = 1
        for j in range(n-1):
            if array[i][j] == array[i][j+1]:
                count += 1
                answer = max(answer, count)
            # 다른 사탕 마주쳤으니 count 초기화
            else:
                count = 1
    # 연속 세로로 되어 있는 사탕 개수 체크
    for j in range(n):
        count = 1
        for i in range(n-1):
            if array[i][j] == array[i+1][j]:
                count += 1
                answer = max(answer, count)
            # 다른 사탕 마주쳤으니 count 초기화
            else:
                count = 1

### 인접한 사탕들은 같던 같지 않던 일단 뒤집어보고 계산함
# 가로로 뒤집기
for i in range(n):
    for j in range(n-1):
        # 인접한 사탕 위치 swap
        array[i][j], array[i][j+1] = array[i][j+1], array[i][j]
        search()
        # swap 한 사탕 위치 제자리로
        array[i][j], array[i][j+1] = array[i][j+1], array[i][j]
# 세로로 뒤집기
for j in range(n):
    for i in range(n-1):
        # 인접한 사탕 위치 swap
        array[i][j], array[i+1][j] = array[i+1][j], array[i][j]
        search()
        array[i][j], array[i+1][j] = array[i+1][j], array[i][j]

print(answer)