문제/프로그래머스
[프로그래머스] [PCCP 기출문제] 2번 / 석유 시추 - Java
icodesiuuuu
2024. 11. 21. 23:23
문제
https://school.programmers.co.kr/learn/courses/30/lessons/250136
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 개요
문제는 세로 n, 가로 m의 격자에서 석유가 묻힌 땅을 분석하여, 수직으로 한 줄 시추관을 설치했을 때 뽑을 수 있는 석유량이 최대가 되는 위치를 찾는 것입니다.
석유는 상하좌우로 연결된 1의 집합(덩어리)로 표현됩니다. 시추관이 지나는 열에서 해당 석유 덩어리에 포함된 모든 석유를 뽑을 수 있습니다.
최종적으로, 각 열에 대해 가능한 석유량을 계산하고 그중 최대값을 반환합니다.
접근 방법
1. 덩어리 구분 및 크기 계산
- 주어진 격자 land에서 석유가 묻힌 영역(값이 1)을 BFS를 사용해 탐색하며 각 석유 덩어리의 크기를 계산합니다.
- 탐색 중 발견된 석유 덩어리를 특정 문자('A', 'B'...)로 표시하여 덩어리를 구분합니다.
- 각 덩어리의 크기는 regionSize라는 해시맵에 저장하여, 나중에 쉽게 크기를 참조할 수 있습니다.
2. 시추관 열별 석유량 계산
- 각 열(column)을 순회하며, 해당 열을 지나는 석유 덩어리들의 크기를 합산합니다.
- 이를 위해, 현재 열에 포함된 유일한 석유 덩어리의 구분 문자를 확인합니다.
- 합산한 석유량을 answer 변수에 저장하고, 이를 계속 업데이트하여 최댓값을 유지합니다.
import java.util.*;
class Solution {
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
static char[][] map;
static boolean[][] visited;
static Map<Character, Integer> regionSize;
public int solution(int[][] land) {
int answer = 0;
int rows = land.length, cols = land[0].length;
map = new char[rows][cols];
visited = new boolean[rows][cols];
regionSize = new HashMap<>();
char region = 'A';
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (land[i][j] == 1 && !visited[i][j]) {
markRegion(i, j, region++, land);
}
}
}
for (int col = 0; col < cols; col++) {
Set<Character> uniqueRegions = new HashSet<>();
for (int row = 0; row < rows; row++) {
if (map[row][col] >= 'A') {
uniqueRegions.add(map[row][col]);
}
}
int sum = uniqueRegions.stream().mapToInt(regionSize::get).sum();
answer = Math.max(answer, sum);
}
return answer;
}
private void markRegion(int startRow, int startCol, char region, int[][] land) {
Queue<int[]> queue = new LinkedList<>();
List<int[]> cells = new ArrayList<>();
queue.add(new int[]{startRow, startCol});
visited[startRow][startCol] = true;
int size = 0;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int r = current[0], c = current[1];
map[r][c] = region;
size++;
cells.add(current);
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < land.length && nc >= 0 && nc < land[0].length
&& land[nr][nc] == 1 && !visited[nr][nc]) {
visited[nr][nc] = true;
queue.add(new int[]{nr, nc});
}
}
}
regionSize.put(region, size);
}
}