https://school.programmers.co.kr/learn/courses/30/lessons/250136
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
세로길이가 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초
효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
풀이
import java.util.*;
import java.lang.*;
class Solution {
static boolean[][] visit;
static int n;
static int m;
static int[] di = {-1, 1, 0, 0};
static int[] dj = {0,0, -1, 1};
static int[][] copyLand;
class Pair{
int i;
int j;
Pair(int i, int j){
this.i=i;
this.j=j;
}
}
class OilLand{ // 석유땅의 면적과 차지하고있는 열번호들
public int area;
public HashSet<Integer> cols;
OilLand(int area, HashSet<Integer> cols){
this.area = area;
this.cols = cols;
}
@Override
public String toString(){
return "area: "+area+", cols:"+cols.toString();
}
}
public int solution(int[][] land) {
n = land.length;
m = land[0].length;
visit= new boolean[n][m];
copyLand = land;
List<OilLand> oilLands = new ArrayList<>(); // 각 석유땅의 면적과 차지하고있는 열번호...
// 계산 끝난 후 oilLands를 검사하며 열마다 어느정도의 면적 가지는지 계산할것
int[] colArea = new int[m];
// 면적 구하기
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(!visit[i][j] && land[i][j]==1){
// System.out.println("섬발견: "+i +", "+j);
HashSet<Integer> cols = new HashSet<>();
oilLands.add(dfs(i, j, new OilLand(0, cols)));
}
}
}
// 모든 석유땅을 돌며 각 석유땅 땅이 차지하는 열이 어디인지 검사 후 모든 열의 정답 구하기
for(OilLand oilLand: oilLands){
// System.out.println("이번 땅은: "+oilLand.toString());
for(int col: oilLand.cols){
colArea[col] += oilLand.area;
// System.out.println(col+"열의 면적이 늘었다=>"+colArea[col]);
}
}
// System.out.println(Arrays.toString(colArea));
return getMax(colArea);
}
// stack DFS
public OilLand dfs(int i, int j, OilLand oilLand){
visit[i][j]=true;
Deque<Pair> stack = new ArrayDeque<>();
stack.offer(new Pair(i, j));
while(!stack.isEmpty()){
Pair p = stack.pollLast();
oilLand.cols.add(p.j);
oilLand.area += 1;
for(int d=0; d<4; d++){
int ni = p.i + di[d];
int nj = p.j + dj[d];
if(ni < 0 || ni>=n || nj<0 || nj>=m || visit[ni][nj] || copyLand[ni][nj]==0) { // 범위검사
continue;
}
visit[ni][nj] = true;
stack.offer(new Pair(ni, nj));
// System.out.println("저는 여기에 있어요: ("+i+", "+ j+")!!!!!");
// System.out.println("다음으로 갈래: ("+ni+", "+nj+")!!!!!");
}
}
// System.out.println(oilLand.toString());
return oilLand;
}
public int getMax(int[] colArea){
int res = Integer.MIN_VALUE;
for(int area : colArea){
if(area>res) res=area;
}
return res;
}
}첫 아이디어
- 모든 덩어리를 dfs로 면적 알아내어
- 그 덩어리의 모든 부분이 몇 번 열에 있는지 작성하면
- 열마다의 덩어리 면적을 알 수 있지 않을까?
단락별 설명
static boolean[][] visit; static int n; static int m; static int[] di = {-1, 1, 0, 0}; static int[] dj = {0,0, -1, 1}; static int[][] copyLand; class Pair{ int i; int j; // Pair(int i, int j){ this.i=i; this.j=j; } } // class OilLand{ // 석유땅의 면적과 차지하고있는 열번호들 public int area; public HashSet<Integer> cols; // OilLand(int area, HashSet<Integer> cols){ this.area = area; this.cols = cols; } @Override public String toString(){ return "area: "+area+", cols:"+cols.toString(); } }
- visit: 방문체크용 배열
- n: land 가로길이
- m: land 세로길이
- di, dj: dfs용
- copyLand: land복사본(dfs에서 쓰기위함)
- Pair: 좌표 행,열의 쌍
- OilLand: 석유가 있는 땅의 면적과 차지하고 있는 열번호들
public int solution(int[][] land) { n = land.length; m = land[0].length; visit= new boolean[n][m]; copyLand = land; // List<OilLand> oilLands = new ArrayList<>(); // 각 석유땅의 면적과 차지하고있는 열번호... // 계산 끝난 후 oilLands를 검사하며 열마다 어느정도의 면적 가지는지 계산할것 int[] colArea = new int[m]; // 면적 구하기 for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(!visit[i][j] && land[i][j]==1){ HashSet<Integer> cols = new HashSet<>(); oilLands.add(dfs(i, j, new OilLand(0, cols))); } } } // // 모든 석유땅을 돌며 각 석유땅 땅이 차지하는 열이 어디인지 검사 후 모든 열의 정답 구하기 for(OilLand oilLand: oilLands){ for(int col: oilLand.cols){ colArea[col] += oilLand.area; } } return getMax(colArea); }
- 모든
OilLand를 저장하기 위해oilLands선언colArea는 각 열 별 얻을 수 있는 석유땅 면적 결과를 가짐- 2중 for문에서는 석유땅 발견 시 dfs로 면적을 알아낸 후
oilLands에 저장한다.- 모든
oilLand들의 정보를 가지고 각 열을 시추하면 얼마나 얻을 수 있을지 저장한다.- 마지막으로 가장 많이 시추할 수 있는 열 값을 반환한다.
// stack DFS public OilLand dfs(int i, int j, OilLand oilLand){ visit[i][j]=true; Deque<Pair> stack = new ArrayDeque<>(); stack.offer(new Pair(i, j)); // while(!stack.isEmpty()){ Pair p = stack.pollLast(); oilLand.cols.add(p.j); oilLand.area += 1; // for(int d=0; d<4; d++){ int ni = p.i + di[d]; int nj = p.j + dj[d]; // if(ni < 0 || ni>=n || nj<0 || nj>=m || visit[ni][nj] || copyLand[ni][nj]==0) { // 범위검사 continue; } visit[ni][nj] = true; stack.offer(new Pair(ni, nj)); } // } return oilLand; }stack을 활용하여 DFS를 전개했다.
Stack collection을 쓰지 않았다. 공식문서에서 말하기를
Deque<Pair> stack = new ArrayDeque();로 선언하면 더 강력하고 안전하다고 한다.
결과
후기 - 런타임 에러가 뜬 이유
public OilLand dfs(int i, int j, OilLand oilLand){
visit[i][j] = true;
oilLand.cols.add(j);
oilLand.area += 1;
for(int d=0; d<4; d++){
int ni = i + di[d];
int nj = j + dj[d];
if(ni < 0 || ni>=n || nj<0 || nj>=m || visit[ni][nj] || copyLand[ni][nj]==0) { // 범위검사
continue;
}
// System.out.println("저는 여기에 있어요: ("+i+", "+ j+")!!!!!");
// System.out.println("다음으로 갈래: ("+ni+", "+nj+")!!!!!");
oilLand = dfs(ni, nj, oilLand);
}
// System.out.println(oilLand.toString());
return oilLand;
}처음에 재귀를 활용한 dfs로 면적을 구했을 때 런타임 에러가 떴다.
재귀의 깊이가 깊어져 발생한 문제라고 판단하여 바로 stack을 이용한 DFS로 변경하였더니 런타임 에러에서 벗어났다.
다른 유저들의 풀이를 보니 BFS로 해결한 사람들이 있다. 관건은 재귀함수를 사용하지 않는 것 같다.
처음엔 쉬운 그래프문제인줄 알았는데 아닌가보다. 방심금지
