[BOJ]3085 - 사탕 게임 (Python)

문제 

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

코드 

import sys
input = sys.stdin.readline

# 행/열에서 사탕 최대 개수 구하는 함수
def check(candies):
    n = len(candies)
    answer = 1

    for i in range(n):
        count = 1
        # 열 순회하면서 연속되는 숫자 세기
        for j in range(1, n):
            if candies[i][j] == candies[i][j-1]:
                count += 1
            else:
                count =1
            if count>answer:
                answer = count

        count = 1
        # 행 순회하면서 연속되는 숫자 세기
        for j in range(1, n):
            if candies[j][i] == candies[j-1][i]:
                count += 1
            else:
                count = 1
            if count>answer:
                answer = count

    return answer


n = int(input())
candies = [list(input()) for _ in range(n)]
answer = 0

for i in range(n):
    for j in range(n):
        # 열 바꾸기
        if j+1 < n:
            candies[i][j], candies[i][j+1] = candies[i][j+1], candies[i][j]

            temp = check(candies)
            if temp > answer:
                answer = temp

            candies[i][j], candies[i][j+1] = candies[i][j+1], candies[i][j]

        # 행 바꾸기
        if i+1 < n:
            candies[i][j], candies[i+1][j] = candies[i+1][j], candies[i][j]

            temp = check(candies)
            if temp > answer:
                answer = temp

            candies[i][j], candies[i+1][j] = candies[i+1][j], candies[i][j]

print(answer)

 

풀이 

거의 처음으로 풀어보는 그리디 문제였다. 

접근 자체를 어떻게 해야할 지 몰라서 질문글과 블로그에서 힌트를 얻고 작성했다. 

가능한 모든 경우를 확인해야 했다. 

• 반복문을 돌면서 인접한 사탕끼리 바꾸고 바꾸었을 때 먹을 수 있는 사탕의 최대 개수를 계산해본다. 
• 계산하는 함수를 빠져나온 뒤에는 다른 상황들도 볼 수 있게 다시 사탕을 제자리로 돌려 놓는다. 
• 열을 바꾸면서 이 과정을 진행하고, 다 끝나면 행을 바꾸면서 이 과정을 다시 진행한다. 
• 모든 과정이 다 끝나면 최대 개수가 답으로 남는다. 

그리디는 어렵다.... 😭