문제 요약
n x m 크기의 땅이 2차원 배열 land로 주어집니다.
1은 석유가 있는 칸입니다.0은 빈 땅입니다.- 상, 하, 좌, 우로 연결된 석유 칸들은 하나의 석유 덩어리입니다.
시추관은 세로 방향으로 열 하나를 끝까지 관통합니다. 어떤 열에 시추관을 설치했을 때, 그 열이 하나의 석유 덩어리라도 지나간다면 해당 덩어리 전체의 석유를 얻을 수 있습니다.
목표는 시추관 하나를 설치해서 얻을 수 있는 최대 석유량을 구하는 것입니다.
핵심 아이디어
각 열마다 직접 시추관을 꽂아 보면서 연결된 석유 덩어리를 매번 탐색하면 같은 덩어리를 여러 번 탐색하게 됩니다.
대신 석유 덩어리를 먼저 하나씩 찾습니다.
석유 덩어리 하나를 찾으면 다음 두 가지를 알 수 있습니다.
- 이 덩어리의 크기
- 이 덩어리가 걸쳐 있는 열 번호들
어떤 덩어리가 여러 열에 걸쳐 있다면, 그 열들 중 어디에 시추관을 꽂아도 이 덩어리 전체를 얻을 수 있습니다.
따라서 덩어리 하나를 찾을 때마다, 그 덩어리가 포함된 모든 열에 덩어리 크기를 더해 주면 됩니다.
접근 과정
land전체를 순회합니다.- 아직 방문하지 않은 석유 칸을 만나면 BFS로 하나의 석유 덩어리를 탐색합니다.
- BFS 중에 덩어리 크기를 세고, 덩어리가 지나가는 열을
set에 저장합니다. - BFS가 끝나면 해당 덩어리가 지나간 모든 열에 덩어리 크기를 더합니다.
- 모든 덩어리를 처리한 뒤, 열별 누적 석유량 중 최댓값을 반환합니다.
Python 코드
from collections import deque
def solution(land):
n = len(land)
m = len(land[0])
visited = [[False] * m for _ in range(n)]
oil_by_col = [0] * m
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for row in range(n):
for col in range(m):
if land[row][col] == 0 or visited[row][col]:
continue
queue = deque([(row, col)])
visited[row][col] = True
oil_size = 0
columns = set()
while queue:
current_row, current_col = queue.popleft()
oil_size += 1
columns.add(current_col)
for dr, dc in directions:
next_row = current_row + dr
next_col = current_col + dc
if not (0 <= next_row < n and 0 <= next_col < m):
continue
if visited[next_row][next_col]:
continue
if land[next_row][next_col] == 0:
continue
visited[next_row][next_col] = True
queue.append((next_row, next_col))
for c in columns:
oil_by_col[c] += oil_size
return max(oil_by_col)코드 설명
visited = [[False] * m for _ in range(n)]
oil_by_col = [0] * mvisited는 이미 탐색한 석유 칸을 다시 방문하지 않기 위해 사용합니다.
oil_by_col은 각 열에 시추관을 설치했을 때 얻을 수 있는 석유량을 저장하는 배열입니다.
if land[row][col] == 0 or visited[row][col]:
continue빈 땅이거나 이미 다른 석유 덩어리 탐색에서 방문한 칸이라면 건너뜁니다.
queue = deque([(row, col)])
visited[row][col] = True새로운 석유 덩어리를 발견했으므로 BFS를 시작합니다. 시작 칸은 바로 방문 처리합니다.
oil_size = 0
columns = set()oil_size는 현재 석유 덩어리의 크기입니다.
columns는 현재 석유 덩어리가 걸쳐 있는 열 번호들을 저장합니다. 같은 열이 여러 번 등장할 수 있으므로 중복을 제거하기 위해 set을 사용합니다.
oil_size += 1
columns.add(current_col)BFS로 칸 하나를 꺼낼 때마다 덩어리 크기를 1 증가시키고, 해당 칸의 열 번호를 기록합니다.
for c in columns:
oil_by_col[c] += oil_size하나의 석유 덩어리 탐색이 끝나면, 이 덩어리가 지나간 모든 열에 덩어리 크기를 더합니다.
예를 들어 크기가 8인 덩어리가 0, 1, 2번 열에 걸쳐 있다면, 세 열 중 어디에 시추관을 꽂아도 이 덩어리 전체를 얻을 수 있습니다. 따라서 oil_by_col[0], oil_by_col[1], oil_by_col[2]에 각각 8을 더합니다.
왜 열마다 직접 탐색하면 안 될까?
시추관 위치를 하나씩 정하고 매번 연결된 석유 덩어리를 탐색할 수도 있습니다.
하지만 이 방식은 같은 석유 덩어리를 여러 열에서 반복해서 탐색할 수 있습니다. 격자의 크기가 커질수록 불필요한 중복 탐색이 많아집니다.
반면 위 풀이는 각 석유 칸을 BFS에서 한 번만 방문합니다. 이후에는 해당 덩어리가 걸친 열에 크기를 누적하기만 하면 됩니다.
시간 복잡도
땅의 세로 길이를 n, 가로 길이를 m이라고 하겠습니다.
각 칸은 BFS 과정에서 최대 한 번만 방문됩니다.
O(n * m)열별 누적 과정은 각 석유 덩어리가 걸친 열에 대해서만 수행됩니다. 전체적으로 격자의 크기에 비례하는 수준에서 처리할 수 있습니다.
정리
이 문제의 핵심은 시추관을 열마다 꽂아 보는 것이 아니라, 석유 덩어리를 먼저 찾는 것입니다.
하나의 석유 덩어리에 대해 크기와 포함된 열들을 구한 뒤, 해당 열들에 석유량을 누적하면 같은 덩어리를 중복 계산하지 않고 효율적으로 답을 구할 수 있습니다.
BFS 또는 DFS로 연결 요소를 찾고, 그 결과를 열 단위로 누적하는 문제라고 볼 수 있습니다.
