[Algorithm] 백준 3085 : 사탕 게임

문제
https://www.acmicpc.net/problem/3085
풀이
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Silver/3085.%E2%80%85%EC%82%AC%ED%83%95%E2%80%85%EA%B2%8C%EC%9E%84/%EC%82%AC%ED%83%95%E2%80%85%EA%B2%8C%EC%9E%84.py

처음 이 문제를 봤을 때 도대체 어떻게 비교를 해야할까.. 싶었다. 어떤 규칙을 찾는 것은 힘들 것 같고, 그냥 일단 해봐야하나? 라는 생각이 들었지만 구현을 어떻게 시작해야할 지 감이 오지 않아 검색을 통해 감을 잡아보고자 했다. 검색을 통해 이 문제가 모든 경우의 수를 찾아봐야하는 브루트포스 알고리즘이라는 것을 확인하고 나서야 구현을 시작했다.

나는 뭔가 규칙을 찾을 수 없을 것만 같은 것이나 확 복잡해질 거라는 것이 느껴지면 일단 하나씩 구현이라도 해보자라는 마음을 잘 갖지 않는 것 같다. 많은 문제들이 규칙보단 그냥 일단 시도해보면서 그 이후에 이런 게 숨어져 있었네 라고 알 확률이 더 클 거 같은데, 이런 점이 부족하다보니 아쉬운 것 같다. 이런 부분에서는 일단 뭐라도 시도해보자 라는 마음가짐을 가져야 할 필요성이 느껴졌다.

다시 문제로 돌아오자면, for 문을 중첩해 사용하면서, 최대 사탕 개수를 구하는 것과 보드를 변경하는 것을 구현하면 됐다. 최대 사탕 개수를 구할 때 같은 행에서 최대 개수를 찾는 것은 쉬웠는데, 열을 기준으로 구하는 것에서는 살짝 헷갈렸었다. 이중 for문에서 항상 바깥 for 문은 행, 안쪽 for 문을 열로 잡고 구현해왔기 때문에 그랬던 것 같다. 이렇게 생각하기 보다는, 어떤 값을 고정시키고 어떤 값을 변화를 줄 것인지로 생각하면 쉽게 판단할 수 있는 문제였다.

최대 사탕 개수를 구하는 함수는 따로 생성한 후, 보드에 변경을 주면서 만든 함수를 실행시켜주었다. 함수를 실행시킨 결과들 중 가장 큰 값을 최종적으로 프린트하게 해주면 문제를 해결할 수 있었다.

이번 문제를 통해 가장 크게 배울 수 있었던 것은 뭐라도 먼저 시도해봐야지 알 수 있다는 것이었다. 미리 겁먹지 말고 시도해보자 !!!

< 풀이 코드 >

#브루트포스 알고리즘 

import sys
input = sys.stdin.readline

N = int(input())
candies = []

for _ in range(N):
    candy_list = input().rstrip()
    candies.append(list(candy_list))

def max_candy(board):
    results = []
    for i in range(N):
        result = 1
        for j in range(N-1):
            if board[i][j] == board[i][j+1]:
                result += 1
            else:
                results.append(result)
                result = 1 
            
            if j == N-2:
                results.append(result)
    for i in range(N):
        result = 1
        for j in range(N-1):
            if board[j][i] == board[j+1][i]:
                result += 1
            else:
                results.append(result)
                result = 1
            
            if j == N-2:
                results.append(result)

    return max(results)

result_list = []

for i in range(N):
    for j in range(N-1):
            if candies[i][j] != candies[i][j+1]:
                candies[i][j], candies[i][j+1] = candies[i][j+1], candies[i][j]
                result_list.append(max_candy(candies))
                candies[i][j], candies[i][j+1] = candies[i][j+1], candies[i][j]

            if j == N-2:
                result_list.append(max_candy(candies))

for i in range(N-1):
    for j in range(N):
            if candies[i][j] != candies[i+1][j]:
                candies[i][j], candies[i+1][j] = candies[i+1][j], candies[i][j]
                result_list.append(max_candy(candies))
                candies[i][j], candies[i+1][j] = candies[i+1][j], candies[i][j]

            if i == N-2:
                result_list.append(max_candy(candies))

print(max(result_list))