Enochkon's blog

문제

코드

import sys
sys.setrecursionlimit(1000000)

def dfs(land, i, j, m, n, check, patch_id):
    if i < 0 or i >= m or j < 0 or j >= n or check[i][j] != 0 or land[i][j] == 0:
        return 0
    check[i][j] = patch_id 
    size = 1  
    
    size += dfs(land, i + 1, j, m, n, check, patch_id)
    size += dfs(land, i - 1, j, m, n, check, patch_id)
    size += dfs(land, i, j + 1, m, n, check, patch_id)
    size += dfs(land, i, j - 1, m, n, check, patch_id)

    return size

def solution(land):
    m = len(land)
    n = len(land[0])
    check = [[0] * n for _ in range(m)]

    patch_sizes = {}
    patch_id = 1

    for i in range(m):
        for j in range(n):
            if land[i][j] == 1 and check[i][j] == 0:
                patch_size = dfs(land, i, j, m, n, check, patch_id)
                patch_sizes[patch_id] = patch_size
                patch_id += 1

    max_oil = 0
    for j in range(n):
        oil_in_column = set()
        for i in range(m):
            if check[i][j] != 0:
                oil_in_column.add(check[i][j])

        total_oil = sum(patch_sizes[pid] for pid in oil_in_column)
        max_oil = max(max_oil, total_oil)

    return max_oil

풀이

• 일자로 팠을 때 석유를 최대한 많이 얻는 경우는?

1. 우선 땅에 있는 모든 석유 웅덩이를 dfs로 확인하여 1,2,3 라벨과 넓이를 붙여준다.
2. 그 뒤 땅을 한번씩 돌면서 일자로 팠을 때 시추 가능한 양을 체크하면서 최대로 시추 가능한 곳의 양을 max_oil에 저장하고 리턴한다.

특이사항

• 우선 정확성은 전부 통과했는데 효율성에러 런타임 에러가 나서 왜그런가 하고 생각해봤는데, 파이썬의 재귀 제한 때문에 오류가 나는것을 파악해서 재귀 허용을 늘려주면 통과한다. (기본 재귀 1000번)
• import sys sys.setrecursionlimit(1000000)
• 원래는 매 시행때 dfs를 돌면서 계속 체크를 하려고 했다가 그렇게 되면 효율성을 통과하지 못할거라고 생각하고 미리 dfs로 모든 석유의 라벨링을 해주며 진행했다.