Softeer Level 3 사물인식 최소 면적 산출 프로그램 Python

문제 링크

https://softeer.ai/practice/6277

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys
sys.setrecursionlimit(10**9)

input = sys.stdin.readline
N, K = map(int, input().split())

def newDfs(S, maxX, minX, maxY, minY):
  global minSize
  if S == K+1:
    nowSize = (maxX - minX) * (maxY - minY)
    if nowSize < minSize:
      minSize = nowSize
    return
  for nextX, nextY in stackK[S]:
    newMaxX = max(maxX, nextX)
    newMinX = min(minX, nextX)
    newMaxY = max(maxY, nextY)
    newMinY = min(minY, nextY)
    newSize = (newMaxX - newMinX) * (newMaxY - newMinY)
    if newSize < minSize:
      newDfs(S+1, newMaxX, newMinX, newMaxY, newMinY)
    
minSize = 4000000
stackK = [[] for _ in range(K+1)]
for _ in range(N):
  x, y, color = map(int, input().split())
  stackK[color].append((x, y))
for x, y in stackK[1]:
  newDfs(2, x, x, y, y)
print(minSize)

풀이 방법

- 백트래킹이라고 볼 수 있다.

- 1부터 K까지의 점을 찾아가는 여정이다.

- 각각 한 번씩 지나면서 마지막 K에 도달하면 값을 추출한다.

- 시간초과를 벗어나자.

    - 이 부분이 백트래킹이라고 봐야할 것 같다.

    - newSize를 측정한다.

    - 이 부분에서 minSize보다 크면 어차피 그 뒤에도 계산할 필요가 없다.

느낀점

- 어려운 문제는 아니지만 일단 시간초과를 어떻게 벗어날지 생각해야 했다.

- 내가 오래 걸려서 풀었길래 더 좋은 방법이 있나 싶어서 다른 사람들 코드를 봤는데 똑같았다.

- 문제를 잘 읽자. 이미 풀었는데 K개의 색깔이 있다는 말을 K가 3일 경우 {1, 9, 20}도 된다는 말로 착각했다.

- 28번 시도 끝에 드디어 성공했다. 몇 번 시도하는 것이 뭐가 중요하냐 풀었다는 것이 중요하지라고 위안 삼았다.