프로그래머스

프로그래머스 공원 풀이: 가장 큰 돗자리 찾기

작성자: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

공원 배치도 park에는 사람이 없는 자리 "-1"과 사람이 있는 자리가 표시되어 있습니다. 가지고 있는 정사각형 돗자리의 한 변 길이 목록 mats가 주어질 때, 사람이 없는 공간에 놓을 수 있는 가장 큰 돗자리의 크기를 구합니다.

돗자리는 회전해도 모양이 같은 정사각형이므로 방향을 따로 고려할 필요가 없습니다. 어떤 돗자리도 놓을 수 없다면 -1을 반환합니다.

문제의 제한은 돗자리 종류 최대 10개, 공원 최대 50×50입니다. 따라서 큰 돗자리부터 각 시작 위치를 확인하고, 해당 위치의 정사각형 영역이 모두 "-1"인지 검사하는 완전탐색으로 해결할 수 있습니다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

큰 크기부터 탐색하는 완전탐색

가장 큰 돗자리를 찾아야 하므로 mats를 내림차순으로 정렬합니다. 큰 돗자리부터 검사하면 처음 배치 가능한 크기를 찾는 즉시 반환할 수 있습니다.

각 돗자리 크기 size에 대해 다음 위치를 모두 시작점으로 시도합니다.

  • 행: 0부터 행의 개수 - size까지
  • 열: 0부터 열의 개수 - size까지

시작점 (row, col)에서 size × size 영역을 순회하면서 모든 값이 "-1"인지 확인합니다. 한 칸이라도 사람이 있는 자리라면 해당 위치에는 놓을 수 없습니다.

왜 큰 돗자리부터 확인하는가

작은 돗자리부터 확인하면 가능한 결과를 찾은 뒤에도 더 큰 크기가 있는지 계속 확인해야 합니다. 반대로 내림차순으로 확인하면 첫 번째 성공 결과가 곧 최댓값입니다.

복잡도

돗자리 종류를 K, 공원의 크기를 R × C, 돗자리 한 변을 S라고 하면 시간 복잡도는 최악의 경우 O(K × R × C × S²)입니다. 추가로 사용하는 공간은 정렬을 제외하면 O(1)입니다.

핵심 관찰

구해야 하는 것은 공원에서 가능한 최대 정사각형이 아니라 mats에 실제로 존재하는 크기 중 배치 가능한 최대값입니다. 따라서 돗자리 크기를 내림차순으로 확인하고, 각 시작점에서 모든 칸이 -1인지 검사하면 첫 성공이 곧 답입니다.

오답 접근과 반례

빈 공간의 최대 정사각형 크기를 구한 뒤 그 값을 그대로 반환하면 틀릴 수 있습니다. 빈 공간이 4×4여도 mats = [3]이라면 놓을 수 있는 돗자리의 답은 4가 아니라 3입니다. 후보 크기 목록을 반드시 기준으로 삼아야 합니다.

3. 문제 해결 코드 (Python)

def solution(mats, park):
    rows = len(park)
    cols = len(park[0])

    for size in sorted(mats, reverse=True):
        for row in range(rows - size + 1):
            for col in range(cols - size + 1):
                can_place = True

                for r in range(row, row + size):
                    for c in range(col, col + size):
                        if park[r][c] != '-1':
                            can_place = False
                            break
                    if not can_place:
                        break

                if can_place:
                    return size

    return -1

구현 포인트

  • sorted(mats, reverse=True)로 큰 돗자리부터 검사합니다.
  • rows - size + 1과 cols - size + 1을 사용해 공원 밖으로 나가는 시작점을 제외합니다.
  • 영역 안에서 사람이 있는 칸을 발견하면 즉시 다음 위치로 넘어갑니다.
  • 가능한 위치를 찾으면 더 작은 돗자리는 볼 필요가 없으므로 바로 반환합니다.
  • 모든 크기와 위치를 확인해도 성공하지 못하면 -1을 반환합니다.

4. 동일한 문제를 어떻게 풀었나 웹검색 하여 요약

공개된 풀이들은 제한 조건에 맞춰 정사각형 영역을 직접 검사하는 완전탐색을 주로 사용합니다. 일부 풀이는 더 큰 빈 정사각형을 먼저 찾은 뒤 mats에 있는 크기 중 최댓값을 선택하는 방식으로 접근합니다.

  • 프로그래머스 공식 문제 페이지는 "-1"인 공간에만 정사각형 돗자리를 놓을 수 있고, 놓을 수 있는 가장 큰 크기를 반환한다고 설명합니다.
  • aotoyae의 Python 풀이는 돗자리 크기를 큰 순서로 확인하고, 각 시작점의 정사각형 영역을 검사하는 방식을 사용합니다.

누적합이나 DP를 사용하면 영역 검사 비용을 줄일 수 있지만, 이 문제의 공원 최대 크기는 50×50으로 작습니다. 따라서 이 글에서는 자료구조를 추가하지 않고 문제의 규칙을 그대로 따라가는 완전탐색을 선택했습니다.

마무리

정사각형을 배치하는 문제에서는 가능한 크기와 시작 위치를 체계적으로 나누어 확인하면 됩니다. 가장 큰 크기부터 검사하고, 각 영역이 모두 빈 공간인지 판단하면 불필요한 계산을 줄이면서도 간단하고 정확하게 답을 구할 수 있습니다.

#완전탐색#프로그래머스#난이도 1