[PCCP 기출문제] 2번 / 석유 시추 - Python

문제 설명

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

세로길이가 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
효율성 테스트 케이스 제한사항
주어진 조건 외 추가 제한사항 없습니다.

 

문제풀이

이번문제는 간단하게 BFS나 DFS를 통해서 필드를 탐색하고,

탐색하는 과정에서 덩어리를 분류해주면 되는 문제이다.

 

따라서 순회하는 과정에서 덩어리의 크기를 계산하는 것과 그 덩어리가 포함되어 있는 열의 값을

고유하게 저장하여 어느 부분을 시추해야 가장 많은 양의 덩어리를 얻을 수 있는지를 계산했다.

 

간단하게 BFS를 응용해서 해결할 수 있는 문제였다.

코드를 얼마나 깔끔하게 작성하느냐에 따라 달라지는 문제였던 것 같다.

정답코드

from collections import deque, defaultdict

def solution(land):
    n, m = len(land), len(land[0])
    visited = [[0] * m for _ in range(n)]  # 방문 체크 배열
    oil_sizes = []  # 각 덩어리의 크기 저장
    oil_columns = defaultdict(list)  # 각 열별 덩어리 번호 저장
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    def bfs(x, y, oil_idx):
        q = deque([(x, y)])
        visited[y][x] = 1
        size = 0  # 현재 덩어리 크기
        columns = set()  # 현재 덩어리가 포함된 열
        
        while q:
            cx, cy = q.popleft()
            size += 1
            columns.add(cx)
            
            for k in range(4):
                nx, ny = cx + dx[k], cy + dy[k]
                if 0 <= nx < m and 0 <= ny < n and not visited[ny][nx] and land[ny][nx] == 1:
                    visited[ny][nx] = 1
                    q.append((nx, ny))
        
        # 각 열에 덩어리 번호 저장
        for col in columns:
            oil_columns[col].append(oil_idx)
        return size

    # 모든 석유 덩어리 탐색
    for y in range(n):
        for x in range(m):
            if land[y][x] == 1 and not visited[y][x]:
                oil_sizes.append(bfs(x, y, len(oil_sizes)))
    
    # 각 열별 최대 석유량 계산
    max_oil = 0
    for col in range(m):
        oil_sum = sum(oil_sizes[idx] for idx in set(oil_columns[col]))
        max_oil = max(max_oil, oil_sum)
    
    return max_oil