석유 시추
Prov
세로 n 가로 m인 맵에 시추관을 수직으로 뜷었을 때 가장 많은 석유를 뽑을 수 있는 시추관의 위치
Solv
(0, 0)부터 석유 위치를 조사하다가 석유가 발견될 경우 상하좌우로 탐색을 진행해서 덩어리 클러스터
탐색 시 위치 x, y를 pop하고 석유가 발견되면 push하며 len(dq)가 0이 될 때까지 반복
클러스터를 진행하며 거친 열의 범위 확보
이 때 한 번 방문했던 곳은 다시 방문하지 않아 연산 중복 방지
크기가 m인 total 중 덩어리가 포함된 열의 범위 pos에 덩어리 갯수를 더해서 각 위치별 석유량 누적
석유량이 가장 많이 누적된 위치 선별
Check
map
n=5
m=8
o 표시된 곳이 석유가 있는 곳
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 | o | o | o | |||||
| 1 | o | o | ||||||
| 2 | o | o | ||||||
| 3 | ||||||||
| 4 |
cluster 1
| sum | pos | dq | x | y |
|---|---|---|---|---|
| [0 3] | ||||
| 1 | 3 | [0 4] | 0 | 3 |
| 2 | 3,4 | [1 4 0 5] | 0 | 4 |
| 3 | 3,4 | [0 5 1 5] | 1 | 4 |
| 4 | 3,4,5 | [1 5] | 0 | 5 |
| 5 | 3,4,5 | [2 5] | 1 | 5 |
| 6 | 3,4,5,6 | [2 6] | 2 | 5 |
| 7 | 3,4,5,6 | [] | 2 | 6 |
Ref
https://velog.io/@seungjae/프로그래머스 [PCCP 기출문제] 2번 / 석유 시추 (Python, BFS)
