🎯문제
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
세로길이가 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 ≤
정확성 테스트 케이스 제한사항
- 1 ≤
land의 길이 = 땅의 세로길이 =n≤ 100- 1 ≤
land[i]의 길이 = 땅의 가로길이 =m≤ 100
- 1 ≤
효율성 테스트 케이스 제한사항
- 주어진 조건 외 추가 제한사항 없습니다.
입출력 예
| 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초
- 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
✏️풀이
코드
import java.util.*;
class Solution {
// 땅의 세로, 가로
static int n, m;
// 열별로 뽑을 수 있는 석유의 양
static int[] oil;
// 좌표이동을 위한 x, y 배열
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
// 방문여부를 저장할 배열
static boolean[][] visit;
// bfs 탐색 메서드
public void bfs(int[][] land, int x, int y) {
// 큐 생성
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x, y});
visit[x][y] = true;
// 탐색의 횟수를 저장
int count = 1;
// 석유가 지나가는 세로열을 저장
Set<Integer> set = new HashSet<>();
// 큐에 값이 없을 때까지 반복
while(!q.isEmpty()) {
int[] now = q.poll();
int nx = now[0];
int ny = now[1];
// set에 탐색하는 열의 위치를 저장
set.add(ny);
for(int i = 0; i < 4; i++) {
int mx = nx + dx[i];
int my = ny + dy[i];
// 범위를 벗어나면 continue
if(mx < 0 || my < 0 || mx >= n || my >= m) {
continue;
}
// 석유가 있으면서 방문한 적 없을 경우
if(land[mx][my] == 1 && !visit[mx][my]) {
// 큐에 값을 넣고 방문여부를 변경, 탐색횟수 증가
q.add(new int[]{mx, my});
visit[mx][my] = true;
count++;
}
}
}
// 모든 탐색이 끝난 뒤 석유가 흐르는 모든 열에 값을 더해줌
for(int index : set) {
oil[index] += count;
}
}
public int solution(int[][] land) {
// 땅의 세로, 가로 저장
n = land.length;
m = land[0].length;
// oil과 visit 배열 생성
oil = new int[m];
visit = new boolean[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
// 석유가 있으면서 방문한 적 없을 경우
if(land[i][j] == 1 && !visit[i][j]) {
// 탐색 시작
bfs(land, i, j);
}
}
}
// oil 배열에 저장된 값 중 가장 큰 값을 반환
return Arrays.stream(oil).max().getAsInt();
}
}설명
bfs 탐색을 사용해서 진행하였다.
땅의 정보를 저장한 배열과 탐색할 시작위치를 매개변수로 받아온다.
bfs 탐색은 큐를 사용해서 진행한다. 따라서 큐를 생성한 뒤에 초깃값인 x, y를 int[]형으로 저장해준다.
큐에 값이 없을 때까지 반복을 진행하며 큐의 값을 하나 가져와서 위치를 옮겨가면서 탐색을 진행한다. 여기서 중요한 점은 석유 덩어리를 탐색하는 것으로 연속된 모든 석유 덩어리의 크기가 count에 저장이 된다.
이때 set은 석유 덩어리가 지나는 세로열의 값들을 저장하는 역할을 하며 중복된 값은 생각할 필요가 없기 때문에 set을 사용하였다.
반복문을 통해 상하좌우의 탐색을 진행하며 범위가 벗어나면 continue를 시켜준다. 만일 석유 덩어리가 연결되어있으면서 방문한 적이 없다면 큐에 값을 넣고 방문여부를 true로 변경해준 뒤 덩어리의 크기를 1 증가 시켜준다.
위의 모든 탐색이 끝나면 set에 저장되어있는 값들을 사용해서 oil 배열에 석유 덩어리의 값을 저장해준다. set에 저장된 값은 index가 되며 oil 배열에 저장되는 값은 해당 열에서 추출할 수 있는 석유의 양이 된다.
solution 메서드에서는 반복문을 사용하여 석유 덩어리를 탐색해준다.
이후 모든 탐색이 종료가 된 뒤, oil 배열에 저장된 값 중 가장 큰 값을 반환해주면 문제를 해결할 수 있다!
💡느낀 점
탐색의 조건을 잘 찾는 것이 중요하구나 느낀 문제였다. 맨 처음 문제를 풀 때는 세로열마다 탐색을 진행하는 방식을 생각하였으나 코드가 복잡하고 같은 석유 덩어리를 여러번 탐색해야하기 때문에 시간의 효율이 떨어질 것 같았다. 따라서 석유 덩어리를 탐색하고 해당 석유 덩어리가 지나가는 세로열에 그 값을 더해주는 방식을 사용했다. 직접 코드를 돌려보진 않았지만 맨 처음 방식과 비교했을 때 탐색의 횟수가 줄기 때문에 시간적 효율이 분명히 좋아지지 않았을까 생각이 들었다. 무작정 적용하는 것보다 어떤 것을 기준으로 탐색할지 먼저 고민해보고 문제를 풀면 좋을 것 같다.
링크
