[알고리즘] 프로그래머스 Lv2 석유 시추

PCCP 기출문제 카테고리로 새롭게 올라온 문제
단계는 Lv2 이다

2차원 배열로 주어진 land에서 석유인 부분은 1로 표시가 되어 있다.
석유인 부분에 시추관을 꽂으면, 이어진 부분의 석유를 모두 추출할 수 있다.
시추관은 열에만 꽂을 수 있다.
시추할 수 있는 최대 석유량을 구해야 한다.

나의 풀이

BFS로 이어진(인접한) 석유 최대량을 구했고, 석유가 있는 열 번호를 저장(col_set)해서
해당 열을 인덱스로 가지는 fuel_col에 석유 최대량을 더해주는 방식으로 풀이했다.

# 프로그래머스 석유 시추

from collections import deque

def solution(land):
    fuel_col = [0] * len(land[0])
    def find_fuel(r, c):
        queue = deque()
        queue.append([r, c])
        land[r][c] = 0
        cnt = 1
        col_set = set()
        while queue:
            x, y = queue.popleft()
            col_set.add(y)
            for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                nx = x + dx
                ny = y + dy
                if (0 <= nx < row) and (0 <= ny < col) and land[nx][ny] == 1:
                    cnt += 1
                    land[nx][ny] = 0
                    queue.append([nx, ny])

        for c in list(col_set):
            fuel_col[c] += cnt

    row = len(land)
    col = len(land[0])

    for r in range(row):
        for c in range(col):
            if land[r][c] == 1:
                find_fuel(r, c)

    answer = max(fuel_col)
    return answer

land = [[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]] # 9
land = [[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]] # 16

print(solution(land))