[프로그래머스] 석유 시추(JAVA)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/250136

---

풀이(25분)

import java.awt.Point;
import java.util.*;
class Solution {
    static int[] answerArr;
    static int[][] direction = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
    static int row;
    static int col;
    static Queue<Point> queue = new LinkedList<>();

    public int solution(int[][] land) {
        int answer = 0;
        answerArr = new int[land[0].length];
        row = land.length;
        col = land[0].length;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(land[i][j] == 1){
                    queue.add(new Point(i,j));
                    land[i][j] = 0;
                    bfs(land);
                }
            }
        }
        int max = 0;
        Arrays.sort(answerArr);
        answer = answerArr[col - 1];
        return answer;
    }

    public static void bfs(int[][] land){ // 석유가 얼만큼 매장되어있는지 탐색
        int count = 0;
        ArrayList<Integer> list = new ArrayList<>(); // 하나의 석유 시추관에 대한 값을 위함
        while (!queue.isEmpty()){
            count++;
            Point nowPoint = queue.poll();
            int nowX = nowPoint.x;
            int nowY = nowPoint.y;
            if(!list.contains(nowY)){ // 그 라인에 대한 석유 시추관을 추적
                list.add(nowY);
            }
            for(int i = 0; i < 4; i++){
                int nextX = nowX + direction[i][0];
                int nextY = nowY + direction[i][1];
                if(nextX >= 0 && nextX < row && nextY >= 0 && nextY < col){
                    if(land[nextX][nextY] == 1){
                        land[nextX][nextY] = 0;
                        queue.add(new Point(nextX, nextY));
                    }
                }
            }
        }

        for(int i : list){ // 하나의 석유 시추관으로 나올 수 있다면
            answerArr[i] += count; // 그 석유 시추관 라인에 대해서는 이 석유 구역의 값을 더해줌
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solution(new int[][] {
                {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}
        }));
    }
}

 

문제의 접근은 단순한 bfs or dfs로 해결할 수 있다. 모른다면 https://to-travel-coding.tistory.com/66 블로그를 참고하자.

 

bfs or dfs로 하나의 석유 area가 얼마만큼의 석유를 보유하고 있는지 알 수 있다고 가정하고 설명을 시작하자.

1. 하나의 석유 시추 구역을 탐사할 때의 값을 게산한다.

2. 이 과정에서 그 석유 구역이 몇번 라인에 해당하는지를 list에 저장해둔다. ( 코드의 ArrayList 부분)

3. 최종적으로 하나의 구역에 대해 탐사를 마쳤다면 해당 라인에 대해서는 전부 그 값을 더해준다.( 그 라인은 해당 석유 구역을 시추할  수 있기 때문이다.)

 

따라서 흐름은 이렇게 된다. 문제의 예제를 따라가보면 1,4 구간에서 bfs를 시작하며 7 만큼의 석유를 팔 수 있음을 bfs로 찾을 수 있다. 이 과정에서 출력을 해보면 다음과 같이 나온다.

nowX = 1 nowY = 4 count = 1
nowX = 1 nowY = 5 count = 2
nowX = 2 nowY = 5 count = 3
nowX = 1 nowY = 6 count = 4
nowX = 2 nowY = 6 count = 5
nowX = 3 nowY = 6 count = 6
nowX = 3 nowY = 7 count = 7

이 때의 x,y좌표 값은 이해를 위해 + 1을 해서 출력한 값이다. 코드 상에서는 0번부터 인덱스를 계산하고 있다.

 

(다시 한번 말하지만 실제로는 3,4,5,6을 넣었다(인덱스 계산을 위해))

여기서 살펴보면 list에는 4,5,6,7이 들어가게 되는 것이다.

그리고 bfs가 최종적으로 7이라는 count값을 측정하면 이 값들을 answerArr 의 4,5,6,7 인덱스에 더해주면 된다.