일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 화장품
- 프로그래머스 알고리즘 공부
- 성분
- C++
- 투자
- C
- 독서
- 자바스크립트
- 알고리즘공부
- 주식
- 프로그래밍언어
- 백준알고리즘
- 알고리즘트레이닝
- 다독
- 책을알려주는남자
- 서평
- 책알남
- 경제
- 지혜를가진흑곰
- 채권
- 재테크
- 돈
- 자바
- JavaScript
- 알고리즘 공부
- Java
- algorithmTest
- 독후감
- algorithmtraining
- algorithmStudy
- Today
- Total
탁월함은 어떻게 나오는가?
[Agorithm] 석유 시추 ( Programmers - PCCP 기출문제 2번 / Python ) 본문
[Agorithm] 석유 시추 ( Programmers - PCCP 기출문제 2번 / Python )
Snow-ball 2024. 2. 27. 21:46문제 설명
세로길이가 n 가로길이가 m 인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.
예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2 입니다.
시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어 나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.
오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.
석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.
제한사항
입출력 예
문제 풀이
python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
from collections import deque
def bfs(land, visit, x, y):
visit[x][y] = 1
count = 1
queue = deque([[x, y]])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
min_y = len(land[0]) - 1
max_y = 0
while queue:
queue_x, queue_y = queue.popleft()
if queue_y < min_y:
min_y = queue_y
if queue_y > max_y:
max_y = queue_y
for i in range(4):
dir_x, dir_y = directions[i]
pivot_x, pivot_y = queue_x + dir_x, queue_y + dir_y
if len(land) - 1 >= pivot_x >= 0 and len(land[0]) - 1 >= pivot_y >= 0 and land[pivot_x][pivot_y] == 1 and visit[pivot_x][pivot_y] == 0:
visit[pivot_x][pivot_y] = 1
queue.append([pivot_x, pivot_y])
count += 1
return [count, min_y, max_y]
def solution(land):
answer = [0 for _ in land[0]]
visit = [[0 for _ in land[0]] for _ in land]
for x in range(len(land)):
for y in range(len(land[0])):
if land[x][y] == 1 and visit[x][y] == 0:
count, mix_y, max_y = bfs(land, visit, x, y)
for i in range(mix_y, max_y + 1):
answer[i] += count
return max(answer)
|
cs |
https://school.programmers.co.kr/learn/courses/30/lessons/250136
'[Snow-ball]프로그래밍(컴퓨터) > Algorithm Training' 카테고리의 다른 글
[Algorithm] 구명보트 ( Programmers / Python && Java ) (1) | 2024.03.06 |
---|---|
[Algorithm] 도넛과 막대 그래프 (Programmers - 2024 KAKAO WINTER INTERSHIP / python ) (0) | 2024.03.04 |
[Algorithm] 붕대 감기 ( Programmers > PCCP 기출문제 1번 / Python ) (1) | 2024.02.12 |
[Algorithm] 데이터 분석 ( Programmers > PCCE 기출문제 10번 / Python ) (0) | 2024.02.07 |
[Algorithm] 이웃한 칸 ( Programmers > PCCE 기출문제 9번 / Python ) (0) | 2024.02.01 |