[PCCP 기출문제] 2번 > 석유 시추 - Python, bfs, 누적합

 

 

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

프로그래머스

 

 

코드 & 풀이

 

from collections import deque

def solution(land):
    n, m = len(land), len(land[0])
    visited = [[False] * m for _ in range(n)]
    
    def find_oil(i, j):
        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        q = deque([(i, j)])
        visited[i][j] = True
        oil_cnt = 0
        min_y, max_y = j, j
        while q:
            nx, ny = q.popleft()
            oil_cnt += 1
            for dx, dy in direct:
                tx, ty = nx + dx, ny + dy
                if 0 <= tx < n and 0 <= ty < m and not visited[tx][ty] and land[tx][ty] == 1:
                    visited[tx][ty] = True
                    q.append((tx, ty))
                    min_y = min(min_y, ty)
                    max_y = max(max_y, ty)
                    
        return [min_y, max_y, oil_cnt]
    
    oils = [0] * m
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and not visited[i][j]:
                min_y, max_y, oil_cnt = find_oil(i, j)
                for idx in range(min_y, max_y + 1):
                    oils[idx] += oil_cnt
    
    return max(oils)

 

 

맨 처음 한 풀이

 

bfs를 사용하고 나서

 

반복문을 통해 한 줄씩 내려가면서 set으로 중복 처리 후

 

합산했다.

 

상당히 비효율적이라고 생각해서

 

다른 방법을 좀 찾아봤다.

 

from collections import deque

def solution(land):
    n, m = len(land), len(land[0])
    
    def counting_oil(oil_cnt, width): # 오일 누적합 처리
        for w in width:
            oils[w] += oil_cnt
    
    def find_oil(x, y): # 오일 크기 찾기
        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        q = deque([(x, y)])
        land[x][y] = 0
        oil_cnt = 0
        width = set()
        
        while q:
            nx, ny = q.popleft()
            oil_cnt += 1
            width.add(ny)
            
            for dx, dy in direct:
                tx = nx + dx
                ty = ny + dy
                
                if 0 <= tx < n and 0 <= ty < m and land[tx][ty] == 1:      
                    land[tx][ty] = 0
                    q.append((tx, ty))
                    
        counting_oil(oil_cnt, width)
        
    oils = [0] * m
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1:
                find_oil(i, j)
    
    return max(oils)

 

크게 달라진 것 없지만 최적화를 해봤다.

 

1. 일단 visited를 뺐다

 

대신에 방문한 곳을 0으로 변경해준다.

 

방문 조건에 land[x][y] == 1일 경우 있기 때문에

 

visited를 사용할 필요가 없어진다.

 

2. 누적합 사용

 

오일의 크기를 구한 후

 

세로로 움직이는 게 아니라

 

len(land[0]), 즉 col 의 길이만큼의 리스트를 생성하고

 

각각의 위치에 오일 크기를 저장한다.

 

이를 위해서 bfs에서 set를 사용해서

 

y값을 저장한 후

 

누적합에 y에 해당하는 위치에 카운트한 오일 수를 더해준다.

 

 

 

이렇게 하니까 속도가 많게는 20퍼센트 향상됐다.

 

 

 

다음에 또 봐요