[프로그래머스/JAVA] PCCP 기출문제 > 2번 > 석유 시추 (by 다알쥐AI)

[석유시추] PCCP 기출문제 > 2번 > 석유 시추

 

 

※ 문제풀이 방법은 다양합니다. 참고만 해주세요 ※

[문제설명]

 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 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

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

 

---

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.

시추관의 위치획득한 덩어리총 석유량

6번 열에 시추관을 설치하면 크기가 2, 1, 1, 12인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 16으로 가장 많습니다. 따라서 16을 return 해야 합니다.

---

제한시간 안내

• 정확성 테스트 : 10초
• 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

 

---

[간단설명]
전형적인 BFS, DFS 문제이다.
각 열마다 시추 했을때, 4방향을 순회하면서 석유의 양을 구하고,
최대 얻을 수 있는 석유의 양을 리턴해 주는 문제이다.
 
[접근방법]
1) 석유덩어리 -> 4방향을 순회하는 로직을 구현(BFS, DFS 모두 가능)
2) 각 행마다, 각 열마다 방문 표시하면서 반복
3) 제외조건 구하기 - 경계 값, 방문했던 곳, 석유가 아닌 곳 제외
4) 탈출조건 계산 - 큐가 비었으면 탈출
 
[주의사항]
1) 각 열마다 행에 중복되는 석유덩어리를 전부 더해 주면 안된다.
2) 각 열마다, 각 행마다 반복하면, 효율성 테스트에서 떨어진다.
3) Map이나 Set을 쓰면 효율성 테스트에서 떨어질 확률이 높아진다.
4) 최대한 반복문은 줄이고, arr이 있는 그대로를 사용하자!
 
[소스공개]

import java.util.*;

class Solution {

    int[] dx={-1,0,1,0}; //x 방향
    int[] dy={0,-1,0,1}; //y 방향
    public int solution(int[][] land) {
        int answer = 0; // max값 리턴
        Queue<int[]> que = new LinkedList<>(); //bfs 큐
        int[] xSum = new int[land[0].length]; //x열 합계
        
        
        for(int x=0;x<land[0].length;x++){ //x열만큼 반복
            for(int y=0;y<land.length;y++){ //y행만큼 반복
                if(land[y][x]==-1 || land[y][x]==0) continue; //방문 했거나, 석유가 아니면 PASS
                que.offer(new int[]{x,y});
                int cnt = 0; //석유덩어리 계산
                int[] xArr = new int[land[0].length]; //**bfs 방문시 x열을 같이 기록(다시 방문 안하기 위함) 
                while(!que.isEmpty()){
                    int[] now = que.poll();
                    int nx = now[0];
                    int ny = now[1];
                    // 1) 경계값을 넘어가거나
                    // 2) 방문했거나
                    // 3) 석유가 아니면 PASS
                    if(nx<0 || ny<0 || nx>=land[0].length || ny>=land.length || land[ny][nx]==-1 || land[ny][nx]==0) continue;
                    cnt++;
                    land[ny][nx] = -1;
                    xArr[nx]=1;
                    
                    // 4방향 모두 방문
                    for(int i=0;i<4;i++){
                        int zx = nx+dx[i];
                        int zy = ny+dy[i];
                        if(zx<0 || zy<0 || zx>=land[0].length || zy>=land.length || land[zy][zx]==-1 || land[zy][zx]==0) continue;
                        que.offer(new int[]{zx,zy});    
                    }
                }
                // **bfs에서 방문했던 경우, 석유덩어리(cnt) 값을, 각 x열에 더해준다
                for(int a=0;a<xArr.length;a++){
                    if(xArr[a]==1){
                        xSum[a] += cnt;
                    }
                }
            }
            answer = Math.max(answer,xSum[x]); // x열중에서 최대값을 구해줌
        }

        return answer;
    }
}

 
[실행결과]