[Lv.2 / 프로그래머스 / 파이썬] 석유 시추 (PCCP 기출문제 2번)

 

 

 

 

프로그래머스

 

 

 

 

 

 

풀이

 

 

BFS로 석유 덩어리의 크기를 구한 뒤 m 만큼 순회하며 세로로 시추관을 설치했을 때 최대의 석유량을 구해야 한다.

 

시추관을 설치할 때마다 해당 부분에 위치한 석유 덩어리의 사이즈를 BFS로 순회한다면 불필요한 연산이 많이 발생할 것이다. 따라서 land를 순회하며 각 석유 덩어리의 사이즈를 측정하고 해당 석유 덩어리에 번호를 붙여주도록 하자. 사이즈를 구했다면 이를 딕셔너리에 담아 번호를 키값으로 조회가 가능하도록 한다.

 

 

def solution(land):
    n, m = len(land), len(land[0])
    direction = [(0,1), (1,0), (0,-1), (-1,0)]
    visited = [[False]*m for _ in range(n)]
    num = 2 # 석유 덩어리에 붙여줄 번호
    size_dict = dict()
    
    # land 를 순회하며 덩어리에 번호를 붙이고 사이즈를 측정
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1:
                # BFS
                q = [(i, j)]
                visited[i][j] = True
                size = 0
                
                while q:
                    x, y = q.pop()
                    land[x][y] = num
                    size += 1
                    for a, b in direction:
                        dx, dy = x+a, y+b
                        if n > dx >= 0 and m > dy >= 0 and land[dx][dy] == 1 and not visited[dx][dy]:
                            visited[dx][dy] = True
                            q.append((dx, dy))
                            
                size_dict[num] = size
                num += 1
    
    # 시추
    ans = 0
    for i in range(m):
        cand = set()
        for j in range(n):
            if land[j][i] != 0:
                cand.add(land[j][i])
        ans = max(ans, sum([size_dict[x] for x in cand]))
    return ans