Search

PGS 석유 시추

태그
그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색
생성일
2024/12/11 12:13

문제 설명

•
N⋅MN \cdot M 크기의 땅에서 석유가 묻힌 여러 덩어리 중, 수직으로 하나의 시추관을 설치해 뽑을 수 있는 최대 석유량을 구하는 문제

예제 입력/출력

land
result
[[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]]
9
[[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]]
16

제약 조건

•
1≤n≤5001 ≤ n ≤ 500
•
1≤m≤5001 ≤ m ≤ 500

문제 풀이

•
노드와 간선의 범위
◦
∣nodes∣≤250,000|nodes| \leq 250,000
◦
∣edges∣≤1,000,000|edges| \leq 1,000,000
접근1 DFS - O(∣nodes∣+∣edges∣))O(|nodes| + |edges|))

풀이 코드

접근1 DFS - O(∣nodes∣+∣edges∣))O(|nodes| + |edges|))