[프로그래머스] 석유 시추

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

프로그래머스

 

처음에는 이중 for 문을 열부터 돌아주면서 방문리스트를 초기화하면서 진행하려고 했고, 테스트 케이스는 다 통과했으나 최적화 부분에서 실패 > deque의 popleft() 사용으로 시간복잡도를 줄였는데도 최적화 통과를 못해서 로직 자체를 손봐야한다는걸 깨달았다. 

bfs처리를 통해 각 열에 영향을 주는 석유덩어리를 미리 만들어두고, 석유덩어리가 영향을 주는 열을 set으로 만들어서 중복을 처리하고 순회하면서 결과값 집합에 size를 더해주었다.

코드

from collections import deque

def solution(land):
    n, m = len(land), len(land[0])
    visited = [[False] * m for _ in range(n)]
    result = [0] * m
    
    def getOil(si, sj):
        di = [0, 1, -1, 0]
        dj = [1, 0, 0, -1]
        q = deque()
        q.append((si, sj))
        visited[si][sj] = True
        size = 1
        affect_col = {sj}
        
        while q:
            ci, cj = q.popleft()
            for k in range(4):
                ni = ci + di[k]
                nj = cj + dj[k]
                if 0 <= ni < n and 0 <= nj < m and not visited[ni][nj] and land[ni][nj] == 1:
                    visited[ni][nj] = True
                    size += 1
                    q.append((ni, nj))
                    affect_col.add(nj)
                    
        for col in affect_col:
            result[col] += size
    
    # 열 이동하면서 시추작업 시작
    for j in range(m):
        for i in range(n):
            if not visited[i][j] and land[i][j] == 1:
                getOil(i, j)
        
    return max(result)