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

https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

 

문제 개요

 

각 열에서 얻을 수 있는 석유 양의 총합 중, 최댓값을 구하는 문제이다.

 

 

알고리즘

 

풀기 위해선 단계를 나눠서 접근하면 좋다.

 

 

1) 한 석유 덩어리에서 얻을 수 있는 석유 양 oil 을 구한다

 

2) 석유 덩어리가 어느 열 사이에 걸쳐있는 지 파악한다

 

3) 2)에서 구한 열에서 뽑을 수 있는 석유 양에 oil을 더한다

 

4) 1~3의 과정을 모든 석유 덩어리에 대해 반복, 결과를 list에 저장

 

5) 4)에서 완성한 list 속 최댓값을 반환한다.

 

 

풀이 

1. 석유 덩어리에서 얻을 수 있는 석유 양 구하기

from collections import deque


def calculate_oil(land, i, j, visited, oil_amount):
    # oil_amount: 열 당 얻을 수 있는 석유의 총량
    # visited: 방문여부 확인
    
    oil = 0                          # 현재 석유덩어리에서 얻을 수 있는 석유량
    n, m = len(land), len(land[0])   # land의 행, 열 수 
    que = deque()                    # BFS 탐색에 필요
    que.append([i, j])               # 시작점을 deque에 넣기
    
    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    
    l, r = j, j     # 현재 보는 석유 덩어리가 걸쳐있는 열
                   # l: 좌측 경계선
                   # r: 우측 경계선
    
    # 1) 석유량 산출
    # 2) 석유 덩어리가 있는 열 구하기
    while que:     # BFS 탐색
        x, y = que.popleft()
        
        if land[x][y] == 1 and visited[x][y] == False:  # 석유가 있고, 방문하지 않은 경우
            visited[x][y] = True   # 방문 처리
            oil += 1               # 석유량 증가
            
            l = min(l, y)    # l 갱신
            r = max(r, y)    # r 갱신
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if (0 <= nx and nx < n) and (0 <= ny and ny < m):       # 영역을 벗어나지 않음
                    if land[nx][ny] == 1 and visited[nx][ny] == False:  # 석유가 있고, 방문하지 않은 경우
                        que.append([nx, ny])   
                    else:          # 그 외
                        continue   # 무시
    
    # 3) oil_amount 에서, 지금 본 석유덩어리가 걸쳐있는 열들에 oil 만큼 더하기
    for i in range(l, r+1):     # 열 구간 [l, r] 사이에서는 oil 만큼 석유를 더 얻을 수 있음
        oil_amount[i] += oil    # oil 만큼 석유량 증가
        
    return [oil, l, r]

 

BFS를 사용하여 한 석유 덩어리에서 얻을 수 있는 석유의 양을 구한다.

이 과정에서 석유 덩어리가 어느 열 사이에 걸쳐있는 지 파악한다. 

 

 

마지막으로, 현재 보고있는 석유 덩어리가 가로지르는 열에서 얻을 수 있는 석유 총량에, 앞서 구한 석유량 "oil"을 더해줘야 한다.

 

2.  열 당 얻을 수 있는 석유 총량 구하기

def solution(land):
    visit_map = [[False for _ in range(len(land[0]))] for _ in range(len(land))]  # 방문여부 저장
    n, m = len(land), len(land[0])
    oil_amount = [0 for _ in range(m)]   # 각 열에서 얻을 수 있는 석유 총량
    
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and visit_map[i][j] == False:        # 석유가 묻혀있고, 방문한 적이 없다면
                calculate_oil(land, i, j, visit_map, oil_amount)    # 석유량 구해서, 가로지르는 열 구간에 그만큼 더하기

 

주어진 "land"를 탐색하며, 방문한 적이 없지만 석유가 있는 칸에 대해서만 석유량을 구하는 등의 작업을 수행한다.

 

3. 최댓값 구하기

    ans = max(oil_amount)   # 열별 얻을 수 있는 석유 총량 중 최댓값
    return ans

 

열 별로 얻을 수 있는 석유량 중 최댓값을 반환한다.

 

 

전체 코드

# 참고한 글: https://velog.io/@seungjae/프로그래머스-PCCP-기출문제-2번-석유-시추-Python-BFS
from collections import deque


def calculate_oil(land, i, j, visited, oil_amount):
    # oil_amount: 열 당 얻을 수 있는 석유의 총량
    # visited: 방문여부 확인
    
    oil = 0                          # 현재 석유덩어리에서 얻을 수 있는 석유량
    n, m = len(land), len(land[0])   # land의 행, 열 수 
    que = deque()                    # BFS 탐색에 필요
    que.append([i, j])               # 시작점을 deque에 넣기
    
    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    
    l, r = j, j     # 현재 보는 석유 덩어리가 걸쳐있는 열
                   # l: 좌측 경계선
                   # r: 우측 경계선
    
    # 1) 석유량 산출
    # 2) 석유 덩어리가 있는 열 구하기
    while que:     # BFS 탐색
        x, y = que.popleft()
        
        if land[x][y] == 1 and visited[x][y] == False:  # 석유가 있고, 방문하지 않은 경우
            visited[x][y] = True   # 방문 처리
            oil += 1               # 석유량 증가
            
            l = min(l, y)    # l 갱신
            r = max(r, y)    # r 갱신
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if (0 <= nx and nx < n) and (0 <= ny and ny < m):       # 영역을 벗어나지 않음
                    if land[nx][ny] == 1 and visited[nx][ny] == False:  # 석유가 있고, 방문하지 않은 경우
                        que.append([nx, ny])   
                    else:          # 그 외
                        continue   # 무시
    
    # 3) oil_amount 에서, 지금 본 석유덩어리가 걸쳐있는 열들에 oil 만큼 더하기
    for i in range(l, r+1):     # 열 구간 [l, r] 사이에서는 oil 만큼 석유를 더 얻을 수 있음
        oil_amount[i] += oil    # oil 만큼 석유량 증가
        
    return [oil, l, r]


def solution(land):
    visit_map = [[False for _ in range(len(land[0]))] for _ in range(len(land))]  # 방문여부 저장
    n, m = len(land), len(land[0])
    oil_amount = [0 for _ in range(m)]   # 각 열에서 얻을 수 있는 석유 총량
    
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and visit_map[i][j] == False:        # 석유가 묻혀있고, 방문한 적이 없다면
                calculate_oil(land, i, j, visit_map, oil_amount)    # 석유량 구해서, 가로지르는 열 구간에 그만큼 더하기
    
    ans = max(oil_amount)   # 열별 얻을 수 있는 석유 총량 중 최댓값
    return ans

 

 

실행 결과