프로그래머스 [PCCP 기출문제] 2번 / 석유 시추 (Python, BFS)

[PCCP 기출문제] 2번 / 석유 시추 바로가기

문제 접근

이 문제는 2가지 단계로 풀었다.

• 석유의 양 구하기
• 정사영하기

문제 풀이

석유의 양 구하기

석유의 양을 구하기 위해서 1인 위치에서 상하좌우로 이어져있는 칸수를 구해야 한다. 이를 위해서 BFS를 사용했다. BFS로 1인 부분을 찾으면 주변을 탐색하면서 1로 이어져있는 칸의 개수를 전부 찾아 count에 저장하게 된다.
이렇게 한덩이의 석유매장량을 구하게 되는 것이다.

def bfs(a, b):
        count = 0
        visited[a][b] = 1
        q = deque()
        q.append((a,b))
        min_y, max_y = b, b
        while q:
            x,y = q.popleft()
            min_y = min(min_y, y)
            max_y = max(max_y, y)
            count += 1
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue
                if visited[nx][ny] == 0 and land[nx][ny] == 1:
                    visited[nx][ny] = 1
                    q.append((nx,ny))

정사영하기

이렇게 한 덩이의 석유매장량을 구하면 우리는 이 석유를 어디에서 시추했을 때 뽑을 수 있을지를 저장해야 한다.
이를 result라는 리스트에 저장한다.
즉 result의 인덱스는 시추하는 열의 번호이고 값은 그 열에서 시추했을 때 뽑을 수 있는 석유량이다.
가장 중요한 생각은 2차원으로 생각하는 것이 아닌 1차원으로 생각하는 것이다. 위아래로 얼마나 많이 분포해 있던지는 시추와는 전혀 관계가 없기 때문이다.
따라서 bfs를 돌면서 석유덩이의 최소 y와 최대 y를 구해서 result라는 리스트에 석유매장량을 저장한다. 이렇게 되면 y부분이 겹치는 석유덩이의 값을 전부 더해서 저장할 수 있게 된다.

 for i in range(min_y, max_y+1):
            result[i] += count

이후에 result 리스트에서 가장 큰 값을 구하면 그것이 한번의 시추에 가장 많이 뽑을 수 있는 석유매장량이다.

제출 코드

from collections import deque
def solution(land):
    answer = 0
    n = len(land)
    m = len(land[0])
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    result = [0 for i in range(m+1)]
    visited = [[0 for i in range(m)] for j in range(n)]
    def bfs(a, b):
        count = 0
        visited[a][b] = 1
        q = deque()
        q.append((a,b))
        min_y, max_y = b, b
        while q:
            x,y = q.popleft()
            min_y = min(min_y, y)
            max_y = max(max_y, y)
            count += 1
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue
                if visited[nx][ny] == 0 and land[nx][ny] == 1:
                    visited[nx][ny] = 1
                    q.append((nx,ny))
        
        for i in range(min_y, max_y+1):
            result[i] += count
    
    for i in range(n):
        for j in range(m):
            if visited[i][j] == 0 and land[i][j] == 1:
                bfs(i,j)
    answer = max(result)
    return answer