[python] 백준 3085 - 사탕 게임

출처 : 백준, https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

 

첫 번째 풀이 : 틀림

 

def forLeftRight(candy, current, visited = None):
  [row, col] = current
  color = candy[row][col]
  count = 0

  for index in range(col, -1, -1):
    if candy[row][index] == color:
      count += 1

      if visited:
        visited[row][index] = 1
        
    else:
      break

  for index in range(col+1, len(candy)):
    if candy[row][index] == color:
      count += 1

      if visited:
        visited[row][index] = 1
        
    else:
      break

  return count

def forUpDown(candy, current, visited = None):
  [row, col] = current
  color = candy[row][col]
  count = 0

  for index in range(row, -1, -1):
    if candy[index][col] == color:
      count += 1

      if visited:
        visited[index][col] = 1
        
    else:
      break

  for index in range(row+1, len(candy)):
    if candy[index][col] == color:
      count += 1

      if visited:
        visited[index][col] = 1
       
    else:
      break

  return count

def forCross(candy, current, visited):
  [row, col] = current
  count = 0
  
  temp1 = forLeftRight(candy, [row, col], visited)
  visited[row][col] = 0
  temp2 = forUpDown(candy, [row, col], visited)
  count = max(temp1, temp2)
        
  return count

def solution():
  candy = []
  max_val = 0
  
  for _ in range(int(input())):
    candy.append(list(input()))
  
  visited = [[0] * len(candy) for _ in range(len(candy))]
  
  for row in range(len(candy)):
    for col in range(len(candy)):
      if not visited[row][col]:
        ret_val = forCross(candy, [row, col], visited)
  
        if ret_val == len(candy):
          print(ret_val)
          return
  
        if max_val < ret_val:
          max_val = ret_val

  for row in range(len(candy)):
    for col in range(len(candy)):
      if col != len(candy) - 1:
        candy[row][col], candy[row][col + 1] = candy[row][col + 1], candy[row][col]
        temp1 = forUpDown(candy, [row, col])
        temp2 = forUpDown(candy, [row, col + 1])
        candy[row][col], candy[row][col + 1] = candy[row][col + 1], candy[row][col]

      if row != len(candy) - 1:
        candy[row][col], candy[row + 1][col] = candy[row + 1][col], candy[row][col]
        temp3 = forLeftRight(candy, [row, col])
        temp4 = forLeftRight(candy, [row + 1, col])
        candy[row][col], candy[row + 1][col] = candy[row + 1][col], candy[row][col]

      if max_val < max(temp1, temp2, temp3, temp4):
        max_val = max(temp1, temp2, temp3, temp4)

  print(max_val)

solution()

 

반례

input:
4
CCYY
PPZZ
YYCY
ZZPP

expected output:
3

output:
2

 

forLeftRight

기준 노드를 기준으로 좌/우로 이어진 사탕의 개수를 검색하여 return하는 함수

 

forUpDown

기준 노드를 기준으로 상/하로 이어진 사탕의 개수를 검색하여 return하는 함수

 

forCross

기준 노드를 기준으로 좌/우와 상/하로 이어진 사탕이 개수를 각각 검색하여 둘 중 최댓값을 return하는 함수

 

solution

input을 받고 먼저 각 노드에 대해 forCross 함수를 실행하고

그 후, 각 노드와 그 다음 노드(우측 노드, 하단 노드)를 교체하고 forCross 함수를 실행해서

각 return 값 중 최댓값을 출력하는 함수

 

좌우로 바뀔 땐 상/하만 검색하고 상/하로 바뀔 땐 좌/우만 검색하도록 알고리즘을 짰는데

반례가 존재했다.

 

 

두 번째 풀이 : 성공

 

def forLeftRight(candy, current):
  [row, col] = current
  color = candy[row][col]
  count = 0

  for index in range(col, -1, -1):
    if candy[row][index] == color:
      count += 1
    else:
      break

  for index in range(col+1, len(candy)):
    if candy[row][index] == color:
      count += 1
    else:
      break

  return count

def forUpDown(candy, current):
  [row, col] = current
  color = candy[row][col]
  count = 0

  for index in range(row, -1, -1):
    if candy[index][col] == color:
      count += 1
    else:
      break

  for index in range(row+1, len(candy)):
    if candy[index][col] == color:
      count += 1
    else:
      break

  return count

def forCross(candy, current):
  [row, col] = current
  count = 0
  
  return max(forLeftRight(candy, [row, col]), forUpDown(candy, [row, col]))

def solution():
  candy = []
  max_val = 0
  
  for _ in range(int(input())):
    candy.append(list(input()))

  for row in range(len(candy)):
    for col in range(len(candy)):
      if col != len(candy) - 1:
        candy[row][col], candy[row][col + 1] = candy[row][col + 1], candy[row][col]
        temp1 = forCross(candy, [row, col])
        temp2 = forCross(candy, [row, col + 1])
        candy[row][col], candy[row][col + 1] = candy[row][col + 1], candy[row][col]

      if row != len(candy) - 1:
        candy[row][col], candy[row + 1][col] = candy[row + 1][col], candy[row][col]
        temp3 = forCross(candy, [row, col])
        temp4 = forCross(candy, [row + 1, col])
        candy[row][col], candy[row + 1][col] = candy[row + 1][col], candy[row][col]

      if max_val < max(temp1, temp2, temp3, temp4):
        max_val = max(temp1, temp2, temp3, temp4)

      if max_val == len(candy):
        print(max_val)
        return

  print(max_val)

solution()

 

forLeftRight

기준 노드를 기준으로 좌/우로 이어진 사탕의 개수를 검색하여 return하는 함수

 

forUpDown

기준 노드를 기준으로 상/하로 이어진 사탕의 개수를 검색하여 return하는 함수

 

forCross

기준 노드를 기준으로 좌/우와 상/하로 이어진 사탕이 개수를 각각 검색하여 둘 중 최댓값을 return하는 함수

 

solution

input을 받고 각 노드와 그 다음 노드(우측 노드, 하단 노드)를 교체하고 forCross 함수를 실행해서
각 return 값 중 최댓값을 출력하는 함수

 

input을 받고 모든 노드를 상하좌우로 살피게 되면서 교체하기 전 먼저 forCross로 살펴볼 필요가 사라졌다.

---

시간 복잡도

-

다른 사람의 풀이를 보면서 알게 된 점

-

고찰

빡구현에서는 내 머리가 아프지 않도록 구현하는게 핵심이다.
복잡한 로직을 구현하려고 하지말고 최대한 잘게 쪼개서 간단간단하게 구현할 수 있도록 만든 후
구현하는 것이 바람직하다.