[PCCP 기출문제] 2번 / 석유 시추
https://school.programmers.co.kr/learn/courses/30/lessons/250136
문제 설명
세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.
오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.
석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.
풀이
- 각 석유를 뽑을 수 있는 열을 구합니다.
- 각 열마다 석유 칸 수를 더해줍니다.
- 최댓값을 구한다.
from collections import deque
def solution(land):
N, M = len(land), len(land[0])
visited = [[False]*M for _ in range(N)]
def BFS(xx, yy, land, visited):
dq = deque([(xx, yy)])
visited[xx][yy] = True
cnt = 1
arr= [yy]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
while dq:
x, y = dq.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < M and land[nx][ny] == 1 and visited[nx][ny] == False:
dq.append((nx, ny))
visited[nx][ny] = True
cnt += 1
arr.append(ny)
return cnt, arr
answer = [0]*M
for i in range(N):
for j in range(M):
if land[i][j] == 1 and visited[i][j] == False:
cnt, arr = BFS(i, j, land, visited)
for n in list(set(arr)):
answer[n] += cnt
return max(answer)