[ Baekjoon : python ] 백준 3085 사탕게임 - 브루트포스

[  BAEKJOON ONLINE JUDGE  ] 3085 사탕게임 _ Python 파이썬

 

" 문제 "

 

www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

---

" 아이디어 "

 

2가지 과정을 거쳐서 문제를 풀 수 있다.

 

1. 인접한 두 사탕을 교환한다. (★연속부분 구한 후 원위치) - N^2

 

행과 열이 N개인 배열에서 임의의 원소 한개를 선택하고 그 원소의 오른쪽 원소, 그리고 아래쪽 원소와 교환한다. (시간복잡도 : N^2)

(왼쪽과 위쪽은 중복이 발생하므로 교환하지 않는다.)

 

 

2. 가장 긴 연속부분 (행 또는 열) 을 구한다.

 

원래 모든 행, 열을 조사하는 것이 정석이지만, 중복을 조금 줄여보자.

a[i][j] 와 a[i+1][j] 의 원소를 교환했다고 가정했을 경우,

실질적으로 연속부분이 변화하는 부분은 총 3줄이다.

i 번째 행, i + 1 번째 행, 그리고 j 번째 열이다.

그러므로 우리는 이 3줄의 연속부분만 구해보면 된다.

 

---

" 코드 "

def check(a, s_row, e_row, s_col, e_col):
  n = len(a)
  result = 1
  # 행 체크
  for i in range(s_row, e_row+1):
    cnt = 1
    for j in range(1, n):
      if a[i][j-1] == a[i][j]:
        cnt += 1
      else:
        cnt = 1
      if cnt > result:
        result = cnt
  # 열 체크
  for i in range(s_col, e_col+1):
    cnt = 1
    for j in range(1, n):
      if a[j-1][i] == a[j][i]:
        cnt += 1
      else:
        cnt = 1
      if cnt > result:
        result = cnt
  return result
        
  
 
n = int(input())
a = [list(input()) for _ in range(n)]
result = 0
 
for i in range(n):
  for j in range(n):
    if j < n-1:
      a[i][j], a[i][j+1] = a[i][j+1], a[i][j] # 좌우교환
      temp = check(a, i, i, j, j+1) # 연속부분 체크
      if temp > result:
        result = temp
      a[i][j], a[i][j+1] = a[i][j+1], a[i][j] # 원위치
    
    if i < n-1:
      a[i][j], a[i+1][j] = a[i+1][j], a[i][j] # 상하교환
      temp = check(a, i, i+1, j, j) # 연속부분 체크
      if temp > result:
        result = temp
      a[i][j], a[i+1][j] = a[i+1][j], a[i][j] # 원위치
 
print(result)

 

---

" 참고자료 "