[PCCE 기출문제] 10번 / 공원 - 2가지 방법

문제 설명
지민이는 다양한 크기의 정사각형 모양 돗자리를 가지고 공원에 소풍을 나왔습니다. 공원에는 이미 돗자리를 깔고 여가를 즐기는 사람들이 많아 지민이가 깔 수 있는 가장 큰 돗자리가 어떤 건지 확인하려 합니다. 예를 들어 지민이가 가지고 있는 돗자리의 한 변 길이가 5, 3, 2 세 종류이고, 사람들이 다음과 같이 앉아 있다면 지민이가 깔 수 있는 가장 큰 돗자리는 3x3 크기입니다.

 

지민이가 가진 돗자리들의 한 변의 길이들이 담긴 정수 리스트 mats, 현재 공원의 자리 배치도를 의미하는 2차원 문자열 리스트 park가 주어질 때 지민이가 깔 수 있는 가장 큰 돗자리의 한 변 길이를 return 하도록 solution 함수를 완성해 주세요. 아무런 돗자리도 깔 수 없는 경우 -1을 return합니다.

 

제한사항
1 ≤ mats의 길이 ≤ 10
1 ≤ mats의 원소 ≤ 20
mats는 중복된 원소를 가지지 않습니다.
1 ≤ park의 길이 ≤ 50
1 ≤ park[i]의 길이 ≤ 50
park[i][j]의 원소는 문자열입니다.
park[i][j]에 돗자리를 깐 사람이 없다면 "-1", 사람이 있다면 알파벳 한 글자로 된 값을 갖습니다.

 

입출력 예

mats = [5,3,2]

park = [["A", "A", "-1", "B", "B", "B", "B", "-1"], ["A", "A", "-1", "B", "B", "B", "B", "-1"], ["-1", "-1", "-1", "-1", "-1", "-1", "-1", "-1"], ["D", "D", "-1", "-1", "-1", "-1", "E", "-1"], ["D", "D", "-1", "-1", "-1", "-1", "-1", "F"], ["D", "D", "-1", "-1", "-1", "-1", "E", "-1"]]

 

result = 3

 

입출력 예 설명
입출력 예 #1

지문과 동일합니다.
cpp를 응시하는 경우 리스트는 배열과 동일한 의미이니 풀이에 참고해주세요.
ex) 번호가 담긴 정수 리스트 numbers가 주어집니다. => 번호가 담긴 정수 배열 numbers가 주어집니다.
java를 응시하는 경우 리스트는 배열, 함수는 메소드와 동일한 의미이니 풀이에 참고해주세요.
ex) solution 함수가 올바르게 작동하도록 한 줄을 수정해 주세요. => solution 메소드가 올바르게 작동하도록 한 줄을 수정해 주세요.

 

def solution(mats, park):
    mats = sorted(mats,reverse=True)
    answer = -1
    
    for mat in mats:
        for i in range(len(park)-mat+1):
            for j in range(len(park[i])-mat+1):
                ok = False
                if all(park[x][y] == '-1' for x in range(i,i+mat) for y in range(j,j+mat)):
                    ok = True
                if ok:
                    answer = mat
                    break
            if answer > -1:
                break
        if answer > -1:
                break
    return answer

def solution(mats, park):
    mats.sort(reverse = True)
    answer = -1
    h = len(park)
    w = len(park[0])
    dp = [[0]*w for _ in range(h)]
    
    for x in range(h):
        for y in range(w):
            if park[x][y] == '-1':
                if x == 0 or y == 0:
                    dp[x][y] = 1
                else:
                    dp[x][y] = min(dp[x-1][y-1],dp[x-1][y],dp[x][y-1])+1
                
    for m in mats:
        if m <= max(map(max,dp)):
            return m
    
    return answer