ballqs 님의 블로그
[Java] 프로그래머스 문제 - [PCCP 기출문제] 2번 / 석유 시추 본문
오늘 풀어본 문제는 좀 많이 어려웠다. 프로그래머스의 [PCCP 기출문제] 2번 / 석유 시추 라는 문제를 풀어보았다.
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.
예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.
시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.
| 시추관의 위치 | 획득한 덩어리 | 총 석유량 |
| 1 | [8] | 8 |
| 2 | [8] | 8 |
| 3 | [8] | 8 |
| 4 | [7] | 7 |
| 5 | [7] | 7 |
| 6 | [7] | 7 |
| 7 | [7, 2] | 9 |
| 8 | [2] | 2 |
오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.
석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.
제한 사항
- 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
- 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
- land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
- land[i][j]는 0 또는 1입니다.
- land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.
정확성 테스트 케이스 제한사항
- 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
- 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100
효율성 테스트 케이스 제한사항
- 주어진 조건 외 추가 제한사항 없습니다.
입출력 예
| 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
문제의 예시와 같습니다.
입출력 예 #2
시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.
| 시추관의 위치 | 획득한 덩어리 | 총 석유량 |
| 1 | [12] | 12 |
| 2 | [12] | 12 |
| 3 | [3, 12] | 15 |
| 4 | [2, 12] | 14 |
| 5 | [2, 12] | 14 |
| 6 | [2, 1, 1, 12] | 16 |
6번 열에 시추관을 설치하면 크기가 2, 1, 1, 12인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 16으로 가장 많습니다. 따라서 16을 return 해야 합니다.
풀이 과정(오답)
이 문제는 아래와 같이 생각하여 진행하고자 했다.
- 열 기준으로 반복문을 돌리고 거기에서 행 기준으로 반복문을 돌리기 위한 설정
※ 열과 행 크기 설정 - BFS 알고리즘을 사용하여 석유 크기 계산
※ 방문 여부를 관리하는 변수를 통해 크기 계산에 이상 없이 하기 위함- 첫번째 위치를 큐에 담기
- 반복문을 통해 큐에서 하나씩 꺼내기
- 4방면을 돌려가면서 석유가 있는지 그리고 방문하지 않은 위치인지 확인
※ 이상 없으면 큐에 담는 작업 및 방문 여부 설정 그리고 석유 크기 증가
- 계산된 크기를 합하여 결과 값과 비교 후 설정
이러한 생각으로 진행하여 코드를 작성하고자 했다.
코드(오답)
import java.util.*;
class Solution {
// 방향 설정 : 동 , 서 , 남 , 북
int[] x = {1 , -1 , 0 , 0};
int[] y = {0 , 0 , 1 , -1};
int rows , cols;
public int solution(int[][] land) {
int answer = 0;
// 행 , 열 크기 설정
rows = land.length;
cols = land[0].length;
for (int col = 0; col < cols; col++)
{
// 열 기준으로 방문 여부를 관리
boolean[][] visit = new boolean[rows][cols];
int hap = 0;
for (int row = 0; row < rows; row++)
{
// 해당 지점(행 , 열)
int target = land[row][col];
// 해당 지점에 1이 담겨 있으면 석유로 판단! 그리고 방문되어 있지 않으면 통과
if (target == 1 && !visit[row][col])
{
hap += bfs(row , col , land , visit);
}
}
// 합의 크기가 결과값보다 크면 설정
if (hap > answer) answer = hap;
}
return answer;
}
// BFS 알고리즘
public int bfs(int startRow , int startCol , int[][] land , boolean[][] visit)
{
// 들어온 시점에서 크기 1
int result = 1;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{startRow , startCol});
// 방문 여부 설정
visit[startRow][startCol] = true;
while (!queue.isEmpty())
{
// 큐에서 꺼내기
int[] xy = queue.poll();
// 4방향으로 반복문 돌기
for (int i = 0; i < 4; i++)
{
int nextRow = xy[0] + x[i];
int nextCol = xy[1] + y[i];
if (nextRow > -1 && nextRow < rows &&
nextCol > -1 && nextCol < cols &&
!visit[nextRow][nextCol] && land[nextRow][nextCol] == 1)
{
// 방문여부를 설정
visit[nextRow][nextCol] = true;
queue.add(new int[]{nextRow , nextCol});
result++;
}
}
}
return result;
}
}
정확성은 전부 정답인데 효율성에서 다 틀려먹었다….
뭐가 문제인지 계속 생각한 끝에 아래와 같이 정리가 되었다.
- 열마다 visit[][]을 초기화하고 BFS로 덩어리 크기 계산
- 열마다 합산할 때 이미 계산된 덩어리를 재계산 → 시간 초과 발생
- 문제점: 같은 덩어리를 여러 열에서 반복 계산, 효율성 떨어짐
그래서 다시 풀어보았다.
풀이 과정(정답)
재계산되지 않도록 해당 지점(행 , 열)에 크기를 알 수 있도록 하기 위해 변수를 만들어 관리하기로 했다.
- sizes[][] 배열: 각 좌표에 해당 덩어리의 ID를 담아, 이미 계산된 덩어리를 다시 계산하지 않도록 관리
- petroleumsizes (HashMap): 덩어리 ID별 크기를 저장하여, 같은 크기라도 다른 덩어리를 구분
- 열별 석유 크기 합 계산 시, 중복 제거를 위해 HashSet 사용
위의 방법을 추가하여 아래와 같은 순서로 진행하고자 했다.
- 열 기준 반복문 수행
- 각 열마다 행 기준으로 반복하며 덩어리를 탐색
- 배열 크기를 기준으로 반복문 설정 (rows, cols)
- 덩어리 탐색 및 ID 부여
- BFS를 통해 덩어리를 탐색
- 각 덩어리에 고유 ID를 부여하고, sizes[][]에 기록
- BFS 수행 후, 덩어리의 크기를 petroleumsizes에 저장
- 열별 덩어리 크기 합 계산
- 각 열에서 등장하는 덩어리 ID를 HashSet으로 관리
- 중복되지 않은 덩어리만 합산하여 열별 합 계산
- 계산된 값 중 최대값을 결과로 설정
- 최종 결과 반환
- 모든 열의 합산 값을 확인 후 최대값을 반환
코드(정답)
import java.util.*;
class Solution {
// 방향 설정 : 동 , 서 , 남 , 북
int[] x = {1 , -1 , 0 , 0};
int[] y = {0 , 0 , 1 , -1};
int rows , cols;
public int solution(int[][] land) {
int answer = 0;
// 행 , 열 크기 설정
rows = land.length;
cols = land[0].length;
// 덩어리별 ID를 부여하여 관리할 변수
// ※ ID로 관리해야하는 이유! 열마다 덩어리 크기가 같을 수 있기에 고유 ID를 부여해야 함
HashMap<Integer , Integer> petroleumsizes = new HashMap<>();
int id = 1;
// 덩어리의 ID를 담을 변수
int[][] sizes = new int[rows][cols];
// 열 기준으로 반복문
for (int col = 0; col < cols; col++)
{
// 행 기준으로 반복문
for (int row = 0; row < rows; row++)
{
// 해당 지점(행 , 열)
int target = land[row][col];
// 해당 지점에 1이 담겨 있으면 석유로 판단! 그리고 덩어리 ID 담을 변수가 초기값(0)일 경우
if (target == 1 && sizes[row][col] == 0)
{
petroleumsizes.put(id , bfs(row , col , land , sizes , id));
id++;
}
}
}
// 각 열마다 석유의 합계
for (int col = 0; col < cols; col++)
{
// 중복 제거를 위한 set 변수
HashSet<Integer> petroleumids = new HashSet<>();
int sum = 0;
// 행 반복문
for (int row = 0; row < rows; row++)
{
// 해당 지점에 ID 고유값
int getid = sizes[row][col];
// ID가 0이 아닐 경우 덩어리가 있음! 그리고 set 변수에 담겨있지 않아야 함
if (getid > 0 && !petroleumids.contains(getid))
{
sum += petroleumsizes.get(getid);
petroleumids.add(getid);
}
}
answer = Math.max(answer , sum);
}
return answer;
}
// BFS 알고리즘
public int bfs(int startRow , int startCol , int[][] land , int[][] sizes , int id)
{
// 들어온 시점에서 크기 1
int size = 1;
// 석유의 행과 열을 담기 위한 변수
List<int[]> cells = new ArrayList<>();
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{startRow , startCol});
// 시작 지점에 id 부여
sizes[startRow][startCol] = id;
while (!queue.isEmpty())
{
// 큐에서 꺼내기
int[] xy = queue.poll();
// 관련 있는 위치 담기
cells.add(xy);
// 4방향으로 반복문 돌기
for (int i = 0; i < 4; i++)
{
int nextRow = xy[0] + x[i];
int nextCol = xy[1] + y[i];
if (nextRow > -1 && nextRow < rows &&
nextCol > -1 && nextCol < cols &&
sizes[nextRow][nextCol] == 0 && land[nextRow][nextCol] == 1)
{
// id 설정
sizes[nextRow][nextCol] = id;
queue.add(new int[]{nextRow , nextCol});
size++;
}
}
}
// 관련 위치에 덩어리 ID 설정
for (int[] cell : cells)
{
sizes[cell[0]][cell[1]] = id;
}
return size;
}
}
효율성까지 검사하는 문제는 처음이였고 많은 공부가 된 문제였다.
접근 방법을 바꾸고 또 바꾸고 그렇게 풀어가면서 정답에 이르렀다. 시간은 많이 걸렸지만 ㅜ
'코딩 공부 > Java' 카테고리의 다른 글
| [Java] Jar 배포와 War 배포의 차이점 (1) | 2025.12.19 |
|---|---|
| [Java] 프로그래머스 문제 - 서버 증설 횟수 (0) | 2025.09.02 |
| [Java] 프로그래머스 문제 - 택배 상자 꺼내기 (1) | 2025.09.01 |
| [Java] 프로그래머스 문제 - 유연근무제 (0) | 2025.09.01 |
| [Java] 프로그래머스 문제 - 미로 탈출 (0) | 2024.11.27 |