[프로그래머스] (python) PCCP 기출문제 2번 석유 시추 풀이

다른 사람들의 풀이와 비교를 하고싶어서 검색을 했지만, 풀이가 아직까지 많지는 않아서 공유를 드립니다

문제

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

프로그래머스

석유 시추 예시

문제는 비교적 간단하죠, 목표는 석유를 가장 많이 시추를 하는 것이고, 시추관이 지나가는 길에 있는 석유는 모조리 끌어 모을 수 있을 때, 어디에 구멍을 뚫을 것인가!

풀이

1. 석유의 양을 기록하는 dictionary (e.g. {'석유id': 석유양}) 를 만든다.
   1. 석유의 양을 측정함과 동시에 석유를 뜻하는 '1' 을 '석유id'로 바꿔준다.
2. 모든 지점 (column) 마다 직선 구멍을 뚫으면서 어떤 '석유id'가 있는지 확인한다.
3. 각 지점마다 만날 수 있는 '석유id'를 통해 얻을 수 있는 최대의 석유량을 찾는다!

from queue import deque
from collections import defaultdict

directions = (0, 1, 0, -1, 0)

def bfs(i, j, n, m, oil, land):
    amount = 1
    land[i][j] = oil
    que = deque([(i, j)])
    while que:
        x, y = que.popleft()
        for d in range(4):
            nx, ny = x + directions[d], y + directions[d+1]
            if 0 <= nx < n and 0 <= ny < m and land[nx][ny] == 1:
                amount += 1
                land[nx][ny] = oil
                que.append((nx, ny))
                
    return amount

def solution(land):
    answer, oil = 0, 2
    n, m = len(land), len(land[0])
    amount_of = defaultdict(int)

    for i in range(n):
        for j in range(m):
            if land[i][j] == 1:
                amount_of[oil] = bfs(i, j, n, m, oil, land)
                oil += 1
                
    for j in range(m):
        oil_types = set([land[i][j] for i in range(n)])
        amount = 0
        for oil in oil_types:
            amount += amount_of[oil]
        answer = max(amount, answer)
    
    return answer