[프로그래머스/Lv.2] 석유 시추 - Python

문제

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

프로그래머스

(세로길이 n * 가로길이 m)인 이차원 리스트 land의 한 열에서 시추할 수 있는 석유 덩어리의 최대값을 구하는 문제이다.
한 열에서 수직으로 꽂아 시추하는데, 해당 열에 있는 석유 덩어리 뿐만 아니라 그 덩어리와 연결된 다른 열의 석유 덩어리도 같이 딸려온다.

리뷰

풀이

인접한 석유 덩어리 수를 구하기 위해 DFS/BFS를 활용할 수 있다. 나는 BFS를 활용했다.

 

각 열에서 뽑을 수 있는 석유 덩어리 수를 저장할 리스트인 oil을 만들었다.
그리고 BFS 함수에서는 석유 덩어리를 탐색할 때 지나가는 열의 index를 set으로 저장했다. 탐색에서 한 열의 여러 블럭을 지나갈 때 index를 중복으로 저장하는 문제를 방지하기 위해서이다. 이를 해당 탐색에서 구한 석유 덩어리 수와 함께 반환한다. 마지막으로 oil의 최댓값을 구하면 된다.

 

정확성과 함께 효율성을 평가하는 문제이기 때문에 함 BFS 함수 호출과 기타 반복문을 최소한으로 줄여야 한다.

 

코드

from collections import deque

def solution(land):
    answer = 0
    n = len(land)
    m = len(land[0])

    # 각 열에서 뽑을 수 있는 석유 덩어리 수
    oil = [0 for _ in range(m)]

    # BFS에서 방문 여부를 저장하기 위한 리스트
    visited = [[False for _ in range(m)] for _ in range(n)]

    for sy in range(n):
        for sx in range(m):
            if land[sy][sx] == 0 or visited[sy][sx] == True:
                continue
            result = bfs(land, sx, sy, visited)
            for i in result[1]:
                oil[i] += result[0]

    answer = max(oil)

    return answer

# BFS: 인접해있는 석유 덩어리 수 구하기 위한 함수
def bfs(graph, sx, sy, visited):
    n = len(graph)
    m = len(graph[0])
    result = [0, []]

    queue = deque()
    queue.append((sx, sy))

    visited[sy][sx] = True
    result[1].append(sx)
    count = 1

    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]

    while(queue):
        vx, vy = map(int, queue.popleft())

        for i in range(4):
            ax = vx + dx[i]
            ay = vy + dy[i]

            if ax < 0 or ax >= m or ay < 0 or ay >= n:
                pass
            elif graph[ay][ax] == 1 and visited[ay][ax] == False:
                queue.append((ax, ay))
                count+=1
                visited[ay][ax] = True
                result[1].append(ax)

    result[0] = count
    result[1] = set(result[1])

    return result