프로그래머스

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

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

반복문으로 후보 크기와 배치 위치, 내부 칸을 차례로 확인해야 하므로 Level 2로 판단했다.

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이다. 후보 크기 목록을 반드시 기준으로 삼아야 한다.

배치 후보를 줄이는 순서

각 후보는 (size, row, col)로 구분되며, 회전이 필요 없는 정사각형이므로 이 세 정보만으로 모든 배치를 표현할 수 있다. size를 내림차순으로 고정한 뒤 한 영역에서 빈 칸이 아닌 셀을 발견하면 해당 후보의 나머지 셀은 확인하지 않고 다음 시작 위치로 넘어간다. 경계 밖 후보를 처음부터 만들지 않고 성공한 크기에서 탐색을 종료하는 두 가지가 후보 공간을 불필요하게 넓히지 않는다.

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을 반환한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 가능한 돗자리 크기와 배치 불가 상황을 확인할 수 있다.

assert solution([2], [["-1", "-1"], ["-1", "-1"]]) == 2
assert solution([3], [["-1", "-1"], ["-1", "-1"]]) == -1

4. 참고 풀이 비교

  • aotoyae의 Python 풀이는 돗자리 크기를 큰 순서로 확인하고, 각 시작점의 정사각형 영역을 검사하는 방식을 사용한다.

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

마무리

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

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