[Python] 프로그래머스 PCCP 기출 - 석유 시추

https://school.programmers.co.kr/learn/courses/30/lessons/250136?language=python3#

프로그래머스

 

풀이

석유가 묻힌 땅에 대한 정보 land가 주어졌을 때 시추관으로 뽑을 수 있는 최대 석유량을 구하는 문제입니다.

 

구획별로 매장된 석유량을 알아내야 하므로 BFS 알고리즘을 생각할 수 있습니다.

임의 열을 선택했을 때 얻을 수 있는 최대 석유량을 구하기 위해, 각 열을 선택했을 때 얻을 수 있는 석유량을 기록해줘야 합니다. 이는, 석유가 매장된 구획의 최소, 최대열을 기록하여 석유량을 누적해주면 됩니다. BFS를 사용하므로 최소, 최대열은 항상 연결되어 있습니다.

 

1. 석유 매장량 알아내기 -> BFS

2. 석유가 매장된 땅의 최소, 최대열을 기록하여 1차원 리스트로 사영시키기 -> BFS 시작 열을 기록한 후 min, max를 사용해 업데이트

from collections import *

dc = [1, 0, -1, 0]
dr = [0, 1, 0, -1]
    
def solution(land):
    answer = 0
    n_col = len(land[0])
    n_row = len(land)
    visited = [[0] * n_col for _ in range(n_row)]
    result = [0 for i in range(n_col)]
    
    def bfs(row, col):
        count = 0 
        visited[row][col] = 1
        q = deque()
        q.append((row, col))
        min_col, max_col = col, col
        while q:
            c_row, c_col = q.popleft()
            # 매장 위치 min, max 열 기록
            min_col = min(min_col, c_col)
            max_col = max(max_col, c_col)
            # 매장량 카운트
            count += 1
        
            for i in range(4):
                nr = c_row + dr[i]
                nc = c_col + dc[i]
                if nr < 0 or nc < 0 or nr >= n_row or nc >= n_col:
                    continue
                    
                if not visited[nr][nc] and land[nr][nc]:
                    q.append((nr, nc))
                    visited[nr][nc] = 1
        # 열 매장량 누적
        for i in range(min_col, max_col+1):
            result[i] += count

    for r in range(n_row):
        for c in range(n_col):
            if not visited[r][c] and land[r][c]:
                bfs(r, c)
            
    return max(result)