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

 

 

문제 : 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)] 
    col_oil = [0] * m
    
    
    def bfs(a, b):
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        
        queue = deque([(a, b)])
        visited[a][b] = True
        size = 0
        columns = set()
        
        while queue:
            x, y = queue.popleft()
            size += 1
            columns.add(y)

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and land[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
        
        for col in columns:
            col_oil[col] += size
    
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and not visited[i][j]:
                bfs(i, j)
    return max(col_oil)

 

 

석유 덩어리의 크기를 계산하기 위해 BFS로 조건 검사하며 돌고, 땅의 열 col_oil에 크기를 누적시키며 더하여 저장한다. 이를 통해 최댓값을 찾아 최적의 시추관 위치를 도출할 수 있다.

 

처음에 문제를 보고 열에 석유 덩어리의 크기를 누적시켜 계산하면 되겠다고 생각하였는데 구현을 어떻게 해야할지 고민이 되었다. queue에서 popleft() 된 y 값을 집합 set()에 넣음으로써 한 열에서 한 덩어리가 중복 저장되지 않게 구현할 수 있다 !