BOJ-백준 3085번 사탕게임

BOJ-백준 3085번 사탕게임

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

3085번: 사탕 게임

✅ Python 정답 코드 입니다. 더보기 클릭!

#import time
n = int(input())
matrix = []

for i in range(n): # 입력 받음
  x = list(input())
  matrix.append(x)

def check_candy(i, j, c):
  # 가장 긴 연속 부분의 행을 찾는다
  max_candy = 0
  candy=1
  for x in range(1,j+1):
    if c != matrix[i][j-x]:
      break
    else:
      candy+=1
  for x in range(j+1,n):
    if c != matrix[i][x]:
      break
    else:
      candy+=1
  # 기록된 최대 사탕보다 크면 갱신한다
  if max_candy < candy:
    max_candy = candy
  candy=1
  # 가장 긴 연속 부분의 열을 찾는다
  for x in range(1,i+1):
    if c != matrix[i-x][j]:
      break
    else:
      candy+=1
  for x in range(i+1,n):
    if c != matrix[x][j]:
      break
    else:
      candy+=1
  # 기록된 최대 사탕보다 크면 갱신한다
  if max_candy < candy:
    max_candy = candy
  return max_candy

#start = time.time()  # 시작 시간 저장
# 스왑 전
result_candy = 0
for i in range(n):
  for j in range(n):
    result=check_candy(i, j, matrix[i][j])
    if result_candy<result:
      result_candy = result
# 가로로 스왑
for i in range(n):
  for j in range(n-1):
    if matrix[i][j] != matrix[i][j+1]:
      matrix[i][j],matrix[i][j+1] = matrix[i][j+1],matrix[i][j]
      #같은 색이 아닌 사탕 스왑 -> 행 열 확인
      result=check_candy(i, j+1,matrix[i][j+1])
      if result_candy<result:
        result_candy = result
      result=check_candy(i, j,matrix[i][j])
      if result_candy<result:
        result_candy = result
      matrix[i][j],matrix[i][j+1] = matrix[i][j+1],matrix[i][j]
# 세로로 스왑
for i in range(n-1):
  for j in range(n):
    if matrix[i][j] != matrix[i+1][j]:
      matrix[i][j],matrix[i+1][j] = matrix[i+1][j],matrix[i][j]
      #같은 색이 아닌 사탕 스왑 -> 행 열 확인
      result=check_candy(i+1, j,matrix[i+1][j])
      if result_candy<result:
        result_candy = result
      result=check_candy(i, j,matrix[i][j])
      if result_candy<result:
        result_candy = result
      matrix[i][j],matrix[i+1][j] = matrix[i+1][j],matrix[i][j]
print(result_candy)
#print("time :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

📌 해설

탐색할 그래프가 최대 2500(50*50)이므로 스왑하는 과정과 최대 사탕을 구하는 과정에 유의하며 해결해야 하는 문제 입니다. 스왑-체크-스왑전으로 되돌리기를 반복하며 최대 사탕을 구합니다. 

 

🚩주의

저는 스왑과정, check함수에서 시간 초과되서 time을 import하고 답을 구하는 시간을 계속 체크했습니다.

스왑하기 전 matrix에서 최대 사탕을 먹을 경우의 수도 있으므로 스왑 전에도 check함수를 돌려줍니다. 

 

#import time
n = int(input())
matrix = []

for i in range(n): # 입력 받음
  x = list(input())
  matrix.append(x)

1. 필요한 변수를 입력받아 n(matrix 크기), matrix에 저장합니다. 

 

#start = time.time()  # 시작 시간 저장
# 스왑 전
result_candy = 0
for i in range(n):
  for j in range(n):
    result=check_candy(i, j, matrix[i][j])
    if result_candy<result:
      result_candy = result

2. 스왑 전 matrix에서 check_candy함수를 돌려 준 뒤 먹을 수 있는 사탕의 갯수를 반환 받아 result에 저장합니다. 

result_candy(현재까지 최대 캔디)보다 크다면 값을 갱신합니다.

 

# 가로로 스왑
for i in range(n):
  for j in range(n-1):
    if matrix[i][j] != matrix[i][j+1]:
      matrix[i][j],matrix[i][j+1] = matrix[i][j+1],matrix[i][j]
      #같은 색이 아닌 사탕 스왑 -> 행 열 확인
      result=check_candy(i, j+1,matrix[i][j+1])
      if result_candy<result:
        result_candy = result
      result=check_candy(i, j,matrix[i][j])
      if result_candy<result:
        result_candy = result
      matrix[i][j],matrix[i][j+1] = matrix[i][j+1],matrix[i][j]
# 세로로 스왑
for i in range(n-1):
  for j in range(n):
    if matrix[i][j] != matrix[i+1][j]:
      matrix[i][j],matrix[i+1][j] = matrix[i+1][j],matrix[i][j]
      #같은 색이 아닌 사탕 스왑 -> 행 열 확인
      result=check_candy(i+1, j,matrix[i+1][j])
      if result_candy<result:
        result_candy = result
      result=check_candy(i, j,matrix[i][j])
      if result_candy<result:
        result_candy = result
      matrix[i][j],matrix[i+1][j] = matrix[i+1][j],matrix[i][j]
print(result_candy)

(*가로로 스왑, 세로로 스왑을 별도로 나눠서 진행했는데 더 좋은 방향성이 있다면 추후 수정해볼 예정입니다.)

3. 가로 행으로 진행하며 사탕색이 다르다면 스왑하도록 이중 for 문을 작성합니다. 

3-1. 스왑하면 check_candy()함수를 진행합니다. 

3-2. 먹을 수 있는 사탕 수를 result에 저장합니다.

3-3. 만약 result_candy(현재까지 갱신된 최대 사탕 수)보다 크다면 갱신합니다.

3-4. matrix[i][j]의 오른쪽(j+1)만 같은지 같지 않은지 검사했기 때문에,

matrix[i][j+1]에서 check_candy()함수를 마찬가지로 진행해주었습니다. 

3-5. 마찬가지로 result_candy(현재까지 갱신된 최대 사탕 수)보다 크다면 갱신합니다.

4. 세로로 스왑도 위와 같은 방법으로 진행합니다.

 

def check_candy(i, j, c):
  # 가장 긴 연속 부분의 행을 찾는다
  max_candy = 0
  candy=1
  for x in range(1,j+1):
    if c != matrix[i][j-x]:
      break
    else:
      candy+=1
  for x in range(j+1,n):
    if c != matrix[i][x]:
      break
    else:
      candy+=1
  # 기록된 최대 사탕보다 크면 갱신한다
  if max_candy < candy:
    max_candy = candy
  candy=1
  # 가장 긴 연속 부분의 열을 찾는다
  for x in range(1,i+1):
    if c != matrix[i-x][j]:
      break
    else:
      candy+=1
  for x in range(i+1,n):
    if c != matrix[x][j]:
      break
    else:
      candy+=1
  # 기록된 최대 사탕보다 크면 갱신한다
  if max_candy < candy:
    max_candy = candy
  return max_candy

5. 행과 열을 별도로 검사하여 최대 사탕 수를 갱신하고 검사가 끝나면 최대 사탕 수를 반환하는 함수입니다.

  for x in range(1,j+1):
    if c != matrix[i][j-x]:
      break
    else:
      candy+=1

5-1. matrix[i][j]를 기준으로 행 왼쪽을 검사합니다. 다른 색의 사탕이 발견되면 종료하고, 같은 색이면 candy수를 1 증가합니다.

 

for x in range(j+1,n):
    if c != matrix[i][x]:
      break
    else:
      candy+=1

5-2. matrix[i][j]를 기준으로 행 오른쪽을 검사합니다. 다른 색의 사탕이 발견되면 종료하고, 같은 색이면 candy수를 1 증가합니다.

# 기록된 최대 사탕보다 크면 갱신한다
  if max_candy < candy:
    max_candy = candy

5-3. 전체 행에서 연속된 부분의 사탕 수가 candy에 저장 되었으므로 사탕 수가 max_candy(기록된 최대 사탕 수)보다 크면 갱신합니다.

  candy=1
  # 가장 긴 연속 부분의 열을 찾는다
  for x in range(1,i+1):
    if c != matrix[i-x][j]:
      break
    else:
      candy+=1
  for x in range(i+1,n):
    if c != matrix[x][j]:
      break
    else:
      candy+=1
  # 기록된 최대 사탕보다 크면 갱신한다
  if max_candy < candy:
    max_candy = candy
  return max_candy

5-4. 열의 위쪽, 아래쪽을 나눠서 행과 같은 방법으로 candy를 구해 max_candy를 갱신할 수 있도록 합니다.

5-5. max_candy를 반환합니다. 

 

::