*****

문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

시추관의 위치	획득한 덩어리	총 석유량
1	[8]	8
2	[8]	8
3	[8]	8
4	[7]	7
5	[7]	7
6	[7]	7
7	[7, 2]	9
8	[2]	2

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

제한사항

•

1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500

◦

1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500

◦

land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.

◦

land[i][j]는 0 또는 1입니다.

◦

land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

정확성 테스트 케이스 제한사항

•

1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100

◦

1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100

효율성 테스트 케이스 제한사항

•

주어진 조건 외 추가 제한사항 없습니다.

Code

def solution(land):
    rows, cols = len(land), len(land[0])
    visited = [[0] * cols for _ in range(rows)]  # visited를 group_id를 저장하는 용도로 사용
    group_sizes = {}  # group_id별 크기를 저장
    group_id = 1

    def dfs(i, j, gid):
        stack = [(i, j)]
        count = 0

        while stack:
            ci, cj = stack.pop()
            # (1) 현재 위치가 범위가 적합하고 (2) 다른 석유 덩어리가 아니며 (3) 석유가 있으면
            if not (0 <= ci < rows and 0 <= cj < cols) or visited[ci][cj] or land[ci][cj] == 0:
                continue
            
            # 석유 덩어리 (gid) 확장
            visited[ci][cj] = gid
            count += 1
            
            # 석유 덩어리 (gid) 근방 탐색
            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ni, nj = ci + di, cj + dj
                stack.append((ni, nj))

        return count

    # 모든 영역을 한 번만 탐색하여 크기 계산
    for i in range(rows):
        for j in range(cols):
            # land[i][j]가 1인 영역의 인근 구간에 대해서는 모두 방문 후 (1) gid 표시 - visted (2) size 기록 - group_sizes
            if land[i][j] == 1 and not visited[i][j]:
                size = dfs(i, j, group_id)
                group_sizes[group_id] = size
                group_id += 1

    # 각 열별로 최대값 계산
    max_oil = 0
    column_group_sum = [0] * cols  # 각 열의 그룹 크기 합을 저장

    for col in range(cols):
        seen_groups = set()  # 이미 계산한 그룹 체크
        current_sum = 0

        for row in range(rows):
            gid = visited[row][col] # 해당 위치의 석유 덩어리 indexing (gid)
            if gid and gid not in seen_groups:  # 해당 위치에 그룹이 있고 아직 계산하지 않은 그룹이면 (gid 가져오기)
                current_sum += group_sizes[gid]
                seen_groups.add(gid) # 중복 계산 방지를 위해

        column_group_sum[col] = current_sum # 각 열마다 총합 기록

    # 모든 열에 대해 최대값 찾기
    max_oil = max(column_group_sum)

    return max_oil
Python
복사

•

ISSUE

◦

무턱대고 dfs를 호출하면 매 열에 대해서 총합 계산을 위해 dfs를 호출하는 비효율을 초래하기 때문에 구간마다 석유 총합을 계산해놓는게 훨씬 더 효율적이다. 