[CodingTest] BOJ3085 사탕게임 ( BruteForce ) With 파이썬

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

3085번: 사탕 게임

 

 

◎ 문제풀이

 

NXN 크기의 사탕상자를 교환하여 같은 색상이 연속된 사탕개수의 최댓값을 탐색하는 문제이다. 시간제한이 1초인데 N의 최댓값이 50이니 반복문으로 완전탐색해도 시간제한에 걸리지 않는다. 

 

1) 사탕상자에서 연속된 같은 색상 사탕개수의 최댓값을 구하는 함수를 만든다. 

2) 인접한 사탕을 교환할 때마다 1)에서 생성한 함수를 호출한다. 

 

브루트포스는 원리는 단순하나 단순한만큼 코드가 길어지므로 구현력을 키워야 한다. 

 

◎ 코드

import sys
input = sys.stdin.readline

n = int(input())
box = [[] for _ in range(n)]

#사탕상자 초기화
for i in range(n) :
  box[i] = list(input().rstrip())

# 연속된 같은 색상 사탕개수의 최댓값을 파악하는 함수
def max_candy(box) :
  max_count = 0
  count = 1
  
  for i in range(n) :
    for j in range(1,n) : # 행탐색
      if box[i][j] == box[i][j-1] :  #색상이 같은 경우
        count += 1
      else : # 색상이 다른 경우
        max_count = max(max_count,count)
        count = 1
    max_count = max(max_count,count)
    count = 1        

    for j in range(1,n) : #열탐색
      if box[j][i] == box[j-1][i] : # 색상이 같은 경우
        count += 1
      else : # 색상이 다른 경우
        max_count = max(max_count,count)
        count = 1
    max_count = max(max_count,count)
    count = 1
    
  return max_count 

# 교환시작
max_count = max_candy(box)

for i in range(n) :
  for j in range(1,n) : # 행탐색
    box[i][j-1],box[i][j] = box[i][j],box[i][j-1] #변경
    max_count = max(max_count,max_candy(box))
    box[i][j-1],box[i][j] = box[i][j],box[i][j-1] #원복

  for j in range(1,n) : # 열탐색
    box[j-1][i],box[j][i] = box[j][i],box[j-1][i] #변경
    max_count = max(max_count,max_candy(box))
    box[j-1][i],box[j][i] = box[j][i],box[j-1][i] #원복

#출력
print(max_count)