[ Programmers - LV2 ] [PCCP 기출문제] 2번 / 석유 시추

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

프로그래머스

 

알고리즘 문제를 오랜만에 포스팅 합니다.

 

그래프 탐색을 이용하는 알고리즘 문제로, 그래프 탐색의 변형 보다는 이용이라고 하는게 맞는 것 같다.

 

처음 문제를 접했을 때는 시간 효율에 대해서는 생각 하지 않고, 풀이에만 집중해서 문제를 풀었더니 효율성 테스트에서 걸려서 자료 구조부터 다시잡고 시작했다. (사실 초기에는 방문 처리도 별도의 자료 구조를 갖고 했는데 효율성에 걸리다 보니 불필요한 코드를 모두 지우는 뜻하지 않은 리팩토링도 진행 했다.

---

📌 분석

주어지는 땅의 크기 N x M 의 크기가 작지 않게 주어지기 때문에 시간 초과 걱정이 조금 된다.

• 1 <= N, M <= 500

중복 연산

• 컬럼별로 탐색하게 된다면 같은 땅을 또 탐색하는 상황이 생길 수 있다.

 

위 두개를 고려하면서 문제를 풀이 했습니다.

---

📌 풀이

위 분석과 같은 이유로 중복되는 그래프 탐색을 최소화 하기 위해서 석유가 있는 땅은 한 번만 탐색하게 설계 하도록 하였습니다.

[ 탐색 순서 ]

각 컬럼 1 ~ 8 은 초기 값은 0 으로 시작 합니다. (시추 가능한 석유가 있는 땅의 크기)

탐색 시작은 (0, 0) 에서 (N, M) 방향으로 석유가 있다면 석유 땅의 크기를 측정 합니다.

 

[ 가장 먼저 탐색하는 땅 ]

위 순서로 탐색하면 가장 먼저 (0, 3) 좌표에서 7 크기의 석유가 있는 땅을 만나게 됩니다.

그래프 탐색을 통해서 (0, 3) 부터 (0, 4), (0, 5), (1, 4), (1, 5), (2, 5), (2, 6) 을 탐색해서 크기 7을 도출 합니다.

 

[ 석유가 포함되는 땅에 시추 가능한 석유 업데이트 ]

y 축이 column 을 뜻하기 때문에 3 ~ 6 컬럼에 도출된 크기 7을 더해줍니다.

 

[ 석유에서 일반 땅으로 변경 ]

더 이상 해당 땅을 탐색할 필요 없기 때문에 일반 땅과 같도록 값을 변경해 줍니다.

(코드 상으로는 그래프 탐색과 동시에 이루어 지지만, 설명에서는 분리해서 설명하기 위해서 순서를 나눴습니다.)

---

📌 코드 - Java

package com.Week13;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Arrays;

public class LV2_250136 {
    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println(
            sol.solution(new int[][]{
                    {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}
            })
        );
    }

    static class Solution {
        public int N;
        public int M;
        public int[] ansArr;
        public int[] dx = {0, 1, 0, -1};
        public int[] dy = {1, 0, -1, 0};

        public int solution(int[][] land) {
            N = land.length;
            M = land[0].length;
            ansArr = new int[M];

            for(int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {
                    if(land[i][j] == 1) {
                        land[i][j] = 0;  // 석유 시작 땅을 일반 땅으로
                        bfs(land, i, j);  // 석유 땅 탐색
                    }
                }
            }

            return Arrays.stream(ansArr).max().getAsInt();
        }

        public void bfs(int[][] land, int srtX, int srtY) {
            Queue<Point> queue = new LinkedList<>();
            Set<Integer> sameArea = new HashSet<>();  // 해당 땅을 시추 가능한 컬럼 번호
            int cnt = 1;  // 땅 크기

            Point srtP = new Point(srtX, srtY);

            queue.add(srtP);
            sameArea.add(srtY);

            while(!queue.isEmpty()) {
                Point curP = queue.poll();

                for(int i = 0; i < 4; i++) {
                    int nextX = curP.x + dx[i];
                    int nextY = curP.y + dy[i];

                    if(isValid(nextX, nextY) && land[nextX][nextY] == 1) {
                        Point nextP = new Point(nextX, nextY);

                        queue.add(nextP);
                        sameArea.add(nextY);
                        land[nextX][nextY] = 0;  // 일반 땅으로 변경
                        cnt++;
                    }
                }
            }

            for(int y : sameArea) {  // 시추 가능한 컬럼들 일괄 업데이트
                ansArr[y] += cnt;
            }
        }

        public boolean isValid(int x, int y) {
            return 0 <= x && x < N && 0 <= y && y < M;
        }

        class Point {
            int x;
            int y;

            public Point(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
    }
}

---

📌 결과

[ 결과 ]