[프로그래머스] PCCP 기출문제 2번

문제

주어지는 2차원 배열 land에 대하여 가장 많은 석유를 얻을 수 있을 때 그 양을 구해라.
land는 (n x m) 2차원 배열이다.

ex)

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]
]

land 배열에서 얻을 수 있는 석유량은 다음과 같다.

이 문제는 두 개의 단계로 생각해 볼 수 있다.
1. 각 영역은 어떻게 나누고 영역별로 얻을 수 있는 석유량은 얼마인가?
2. 시추관을 관통하였을 때 각 col에 대해 얻을 수 있는 석유량은 얼마인가?

첫번째는 bfs를 통해 얻을 수 있다. (일단 주석 부분은 신경 X)

def bfs(x, y, visited, n, m, land, result):
	queue = deque([(x, y)])
    visited[x][y] = True
    areaOilAmount = 0
    # startY, endY = sys.maxsize, -sys.maxsize

    while queue:
        cx, cy = queue.popleft()
        areaOilAmount += 1
        # startY, endY = min(startY, cy), max(endY, cy)

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx = cx + dx
            ny = cy + dy

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and land[nx][ny] == 1:
                queue.append((nx, ny))
                visited[nx][ny] = True
    
    # for col in range(startY, endY + 1):
        # result[col] += areaOilAmount

두번째는 주석된 부분을 살펴보면 알 수 있다. 시추관은 col을 기준으로 뚫게 된다.
즉, 0열부터 m-1열까지 길이 m짜리 배열을 선언해 두고, 각 영역별로 석유량을 구할 때 영역이 차지하는 col범위에 대해 누적시켜주면 된다.

전체코드

import sys
from collections import deque

def solution(land):
    n = len(land)	# n x m 행렬
    m = len(land[0])
    visited = [[False for _ in range(m)] for _ in range(n)]
    result = [0 for _ in range(m)]	# 각 col에 대해 시추관을 뚫었을 때 얻을 수 있는 석유량
    answer = 0

    for i in range(n):
        for j in range(m):
            if not visited[i][j] and land[i][j] == 1:
                bfs(i, j, visited, n, m, land, result)

    answer = max(result)	# 가장 많은 석유량

    return answer

def bfs(x, y, visited, n, m, land, result):
    queue = deque([(x, y)])
    visited[x][y] = True
    areaAmount = 0
    startY, endY = sys.maxsize, -sys.maxsize	# 영역이 차지하는 col의 범위

    while queue:
        cx, cy = queue.popleft()
        areaAmount += 1
        startY, endY = min(startY, cy), max(endY, cy)

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx = cx + dx
            ny = cy + dy

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and land[nx][ny] == 1:
                queue.append((nx, ny))
                visited[nx][ny] = True
    
    for col in range(startY, endY + 1):	# 해당 col범위에 대해 석유량 누적
        result[col] += areaAmount