프로그래머스 고득점kit [PCCP 기출문제] 2번 석유 시추 | Python
🔎 문제 설명
💚 Level 2
- 난이도 ★★☆☆ - 그래프탐색 BFS
최근 동해에 140억 배럴에 달하는 석유가 묻혀 있을 가능성이 높다는 뉴스를 보았다. 프로그래머스에서 무슨 문제를 풀까 둘러보다가 마침 석유 시추 문제가 보여 풀어보았다.
해당 문제는 기본적인 그래프탐색에 조건을 하나 더 넣은 문제다. 나는 그래프탐색으로 먼저 석유량을 측정하고 (석유량 측정), 시추관을 움직이면서 뽑을 수 있는 석유량을 더해주는 (시추관 뚫기) 방식으로 문제를 해결하였다. 코드는 밑에 첨부해놓았다.
사실 더 고민한다면 여기서 더 나은 풀이 방식으로 해결할 수 있을 것 같다. 조금 더 생각해보고 다른 풀이도 추가하러 와야지!
💻 내 코드
from collections import deque, defaultdict
visited = [[0 for _ in range(500)] for _ in range(500)]
def bfs(x,y,init,land):
dx = [0,0,1,-1]
dy = [1,-1,0,0]
cnt = 1
n, m = len(land), len(land[0])
queue = deque([(x,y)])
visited[x][y] = init
while queue:
x, y = queue.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]:
if not visited[nx][ny]:
queue.append((nx,ny))
visited[nx][ny] = init
cnt += 1
return cnt
def solution(land):
answer = 0
n,m = len(land), len(land[0])
init = 1
oils = defaultdict(int)
# 석유량 측정
for i in range(n):
for j in range(m):
if land[i][j] and not visited[i][j]:
oils[init] = bfs(i,j,init,land)
init += 1 # 석유존 숫자로 구분
# 시추관 뚫기
for i in range(m):
total = 0
selected = []
for j in range(n):
oil_num = visited[j][i]
if land[j][i] and oil_num not in selected:
total += oils[oil_num]
selected.append(oil_num)
answer = max(answer, total)
return answer
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).