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;
    }
}

첫 아이디어

1. 모든 덩어리를 dfs로 면적 알아내어
2. 그 덩어리의 모든 부분이 몇 번 열에 있는지 작성하면
3. 열마다의 덩어리 면적을 알 수 있지 않을까?

단락별 설명

	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로 해결한 사람들이 있다. 관건은 재귀함수를 사용하지 않는 것 같다.

처음엔 쉬운 그래프문제인줄 알았는데 아닌가보다. 방심금지