[Python 문제 풀이] 프로그래머스 '[PCCP 기출문제] 2번 / 석유 시추'

공간적으로 생각해야 함

프로그래머스 Lv.2 '석유 시추' 파이썬 코드 및 풀이

조건파악

1. 시추관이 지난 덩어리는 다 채굴됨

2. 땅의 크기는 최대 500x500 -> 최소 연산 횟수 250,000이다.

접근

BFS로 각 덩어리의 크기를 구해야겠다. 그러고 나서 덩어리의 좌우 가장 끝에 있는 부분의 column 좌표를 기록하자. 이 범위에 시추관이 들어오면 그 때 덩어리의 크기를 더하면 된다. 면적이 크지 않아 중간에 이런 저런 연산이 추가되어도 넉넉하게 풀 수 있겠다.

의사코드

BFS로 각 덩어리의 크기를 구한다.

BFS 로직 안에 덩어리의 좌우 양 끝의 column좌표를 기록하는 로직을 추가한다.

덩어리 하나를 다 구하고 나면 땅의 column 수에 맞게 만들어 놓은 배열에다가 덩어리 좌우 좌표를 범위로 하는 위치에 덩어리 크기를 sum 해놓는다.

제일 sum이 큰 값을 선택한다.

구현

from collections import deque

def solution(land):
    m,n = len(land), len(land[0])
    v = [[False for _ in range(n)] for _ in range(m)]
    d = [(-1,0),(1,0),(0,-1),(0,1)]
    answer_can = [0 for _ in range(n)]
    
    # Seek chunks using BFS
    for i in range(m):
        for j in range(n):
            if not v[i][j] and land[i][j] == 1:
                v[i][j] = True
                path = deque([(i,j)])
                count = 0
                col = [500,-1]
                
                # BFS
                while path:
                    p = path.popleft()
                    count += 1
                    
                    # Record chunk's min/max column coordinates
                    col[0] = p[1] if p[1] < col[0] else col[0]
                    col[1] = p[1] if p[1] > col[1] else col[1]
                    
                    for k in range(4):
                        pp = (p[0]+d[k][0],p[1]+d[k][1])
                        if 0 <= pp[0] < m and 0 <= pp[1] < n and land[pp[0]][pp[1]] == 1 and not v[pp[0]][pp[1]]:
                            path.append(pp)
                            v[pp[0]][pp[1]] = True
                
                # Sum chunks' volume to each column which contains them
                for x in range(col[0],col[1]+1):
                    answer_can[x] += count
    
    return max(answer_can)

[Python 문제 풀이] 프로그래머스 '[PCCP 기출문제] 4번 / 수레