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

[문제]

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

프로그래머스

def solution(board):
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    n, m = len(board), len(board[0])
    oil_pools = [] # 석유 웅덩이 (크기, y범위)

    def DFS(x, y, visited):
        nonlocal count
        nonlocal rangeY
        stack = [(x, y)]
        visited[x][y] = True

        while stack:
            cx, cy = stack.pop()
            rangeY.add(cy)
            for dx, dy in direction:
                nx, ny = cx + dx, cy + dy
                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and board[nx][ny] == 1:
                    visited[nx][ny] = True
                    stack.append((nx, ny))
                    count += 1

    visited = [[False] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and board[i][j] == 1: # 석유 덩어리 발견
                count = 1 # 개수
                rangeY = set()
                DFS(i, j, visited) # 탐사 시작
                oil_pools.append((count, min(rangeY), max(rangeY))) # 덩어리 총 개수 + y축 범위

    # 최대 석유를 뽑아보자
    events = []
    for size, start_y, end_y in oil_pools:
        events.append((start_y, size))
        events.append((end_y+1, -size))
    
    events.sort()
    
    max_oil = 0
    current_oil = 0
    for y, change in events:
        current_oil += change
        max_oil = max(current_oil, max_oil)
    
    return max_oil

 

 

[풀이]

해당 문제를 원래 재귀함수를 통해 DFS(깊이우선탐색)를 구현하여 진행하려고 했으나 효율성을 고려해야 하기에 stack을 활용하여 재귀호출 제거하고 DFS를 구현하였다.

 

각 석유 웅덩이를 발견할 때마다 그 크기와 y축의 시작점, 끝점을 저장

 

저장이 끝났다면 각 웅덩이를 순회하면서 (시작점, 크기변화) / (끝점+1, 크기변화) 과 같이 y축별로 크기변화 이벤트를 저장해줌. 이를 정렬하면 y축 기준으로 오름차순으로, y축이 같다면 크기변화를 기준으로 오름차순으로 만들어줌. 그렇게 정렬한 뒤 순회하면서 현재 y축에서의 오일 (current_oil) 의 크기변화를 계산하고 이를 max_oil과 비교하여 더 크다면 갱신

 

처음에는 모든 y축을 돌면서 또 모든 웅덩이를 순회하였는데 이는 굉장히 비효율적임. 효율성 테스트에서 시간초과가 뜸.그래서 y 좌표별로 석유량의 변화 이벤트를 기록하고 정렬함. 그런 다음 정렬된 순서로 y 좌표를 탐색하고 석유량의 변화를 실시간으로 누적. 현재 y 좌표에서 총 석유량 계산하고 최댓값 갱신 (스위핑 알고리즘)

 

아래는 BFS(너비우선탐색)으로 구현한 코드다.

from collections import deque

def solution(board):
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    n, m = len(board), len(board[0])
    oil_pools = []  # 석유 웅덩이 (크기, y범위)

    def BFS(x, y):
        nonlocal count
        queue = deque()
        queue.append((x, y))
        visited[x][y] = True

        while queue:
            cx, cy = queue.popleft()
            rangeY.add(cy)
            for dx, dy in direction:
                nx, ny = cx + dx, cy + dy
                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and board[nx][ny] == 1:
                    count += 1
                    visited[nx][ny] = True
                    queue.append((nx, ny))

    visited = [[False] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and board[i][j] == 1:  # 석유 덩어리 발견
                count = 1  # 개수
                rangeY = set()
                BFS(i, j)  # 탐사 시작
                oil_pools.append((count, min(rangeY), max(rangeY)))  # 덩어리 총 개수 + y축 범위

    # 최대 석유를 뽑아보자
    events = []
    for size, start_y, end_y in oil_pools:
        events.append((start_y, size))
        events.append((end_y + 1, -size))

    events.sort()

    max_oil = 0
    current_oil = 0
    for y, change in events:
        current_oil += change
        max_oil = max(current_oil, max_oil)

    return max_oil