[프로그래머스] Lv.2 석유 시추 해결 과정(Java)
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
세로길이가 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 해야 합니다.
제한시간 안내
- 정확성 테스트 : 10초
- 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
처음에 확인했을 때, bfs만 수행하면 되겠군 생각해서, 각 라인별로 bfs로 탐색을 했습니다.
for(int w = 0; w < land[0].length; w++) {
//매 라인에서 시추관을 새로 넣음.
visited = new boolean[land.length][land[0].length];
int count = 0;
for(int d = 0; d < land.length; d++) {
if(!visited[d][w] && land[d][w] == 1) {
count += search(land, d, w);
}
}
answer = Math.max(count, answer);
}하지만, 테스트 케이스와 정확성 테스트에서는 문제가 없었지만 효율성 테스트에서 싹 다 틀려서 방법을 고민하게 되었습니다. 코드를 살펴보고 나니, 매 라인에서 직접 석유의 양을 탐색하다 보니 시간이 많이 소요될 수밖에 없던 것을 확인했습니다.
그래서 bfs 탐색 과정을 최소화 하는 방법을 생각해 보긴 했지만, 생각보다 잘 떠오르지 않았습니다. 그러다 시추한 지역에 각각 번호를 매기면 탐색의 시간을 많이 줄일 수 있다고 해서 한번 그 방법 대로 해봤습니다.
int[][] map = new int[rows][cols]; //시추 지역번호를 저장하는 변수
그리고 bfs 탐색을 하고 나서 각 라인에서 얻을 수 있는 석유량 중 최대값을 구하여 해결했습니다.
전체 코드
import java.util.*;
class Solution {
//이미 추출한 지역인지 체크하는 변수
private boolean[][] visited;
//각 라인의 시추 지역 번호를 저장하는 변수
private final Set<Integer> set = new HashSet<>();
public int solution(int[][] land) {
int rows = land.length;
int cols = land[0].length;
visited = new boolean[rows][cols];
int[][] map = new int[rows][cols]; //시추 지역번호를 저장하는 변수
List<Integer> oilCount = new ArrayList<>();
//bfs로 각 시추 지역의 번호 생성 및 추출량 반환
for(int w = 0; w < land[0].length; w++) {
for(int d = 0; d < land.length; d++) {
if(!visited[d][w] && land[d][w] == 1) {
int count = search(land, d, w, oilCount.size()+1, map);
oilCount.add(count); //추출량 저장
}
}
}
return getMaxCount(map, oilCount, rows, cols);
}
private int getMaxCount(int[][] map, List<Integer> list, int rows, int cols) {
int max = 0;
//각 라인에 대해서 시추 시 최대가 되는 추출량 계산
for(int col = 0; col < cols; col++) {
int count = 0;
for(int row = 0; row < rows; row++) {
if(map[row][col] > 0) {
set.add(map[row][col]);
}
}
for (Integer id : set) {
count += list.get(id-1);
}
max = Math.max(max, count);
set.clear();
}
return max;
}
//bfs 수행
private int search(int[][] land, int d, int w, int oilId, int[][] oilMap) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{d, w});
visited[d][w] = true;
oilMap[d][w] = oilId;
int[] dd = {0, 0, 1, -1};
int[] dw = {1, -1, 0, 0};
int count = 0;
while(!queue.isEmpty()) {
int size = queue.size();
count += size;
for(int i = 0; i < size; i++) {
int[] poll = queue.poll();
int curr_d = poll[0];
int curr_w = poll[1];
for(int j = 0; j < 4; j++) {
int new_d = curr_d + dd[j];
int new_w = curr_w + dw[j];
if(isValid(new_d, new_w, land.length, land[0].length)
&& !visited[new_d][new_w]
&& land[new_d][new_w] == 1) {
visited[new_d][new_w] = true;
oilMap[new_d][new_w] = oilId;
queue.offer(new int[]{new_d, new_w});
}
}
}
}
return count;
}
private boolean isValid(int d, int w, int depth, int width) {
return d >= 0 && d < depth && w >= 0 && w < width;
}
}정리 & 생각
- bfs 탐색을 최소화할 필요가 있는 경우, 탐색 지역에 번호를 매겨보자
- (dfs 탐색도 감떨어지기 전에 해봐야 하는데..)