[프로그래머스] Java Lv2. 코딩테스트 연습 > PCCP 기출문제 > 석유 시추 (BFS 예제)

문제설명

세로 길이가 n, 가로 길이가 m인 격자 모양의 땅 속에 여러 덩어리로 나누어 묻혀있는 석유가 있다.

수직으로 단 하나의 시추관을 뚫었을 때 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾아라.

제한사항

• 1 <= land의 길이 = 땅의 세로길이  = n <= 500
• 1 <= land[i]의 길이 = 땅의 가로길이 = m <= 500
• land[i][j]는 i+1 행 j+1 열 땅의 정보를 나타냄
• land[i][j]는 0 이면 빈 땅을, 1 이면 석유가 있는 땅을 의미

접근방법

효율성 테스트를 하는 것으로 보아 시추관의 위치를 옮기며 전체 탐색을 하는 것이 아닌 오일의 위치에 대한 정보를 먼저 파악하는 것이 필요하다 -> BFS를 사용한다

land를 순차적으로 탐색하면서 석유(1)를 발견하면 해당 덩어리에 id를 부여하고 연결된 석유의 총 량을 파악한다.

시추관을 옮기면서 해당 위치에 존재하는 석유 id를 통해 석유 총 량 합계를 내서 최댓값을 구한다.

핵심로직

• 석유가 발견되는 순서대로 2부터의 숫자를 부여해서 석유 덩어리를 indexing한다.
  • 0, 1은 이미 land에 부여되어 있는 숫자이다.
  • 0, 1이 아닌 숫자는 이미 탐색이 완료된 석유이므로 탐색할 필요가 없다.
  • 문제로 주어지는 매개변수를 변경하므로 좋은 방법은 아니다.
• BFS를 활용하여 최초 발견된 석유의 id를 설정한 석유로부터 연결된 석유를 파악해 석유 덩어리 총량을 구하고 전부 해당 id로 바꿔준다.
  • 큐를 생성해 탐색할 석유 좌표를 관리한다.
  • 해당 위치에 석유가 발견되면(1) 현재 탐색중인 석유 덩어리의 id를 부여하고, 석유 총량 리스트.get(id)에 +1 해준다.
  • 석유가 발견된 위치의 상, 하, 좌, 우 좌표를 큐에 넣어 탐색을 계속한다.
• 그렇게 탐색된 석유의 양을 id에 해당하는 list에 저장한다.
• 시추관을 1부터 m까지 옮기며 해당 열에 있는 석유 id를 파악한 후 리스트에서 석유 총량의 합을 구한다.

입출력 예

• land = [[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]]
• result = 9

코드 작성

import java.util.*;

class Solution {
    // 각 석유 지역의 석유 양을 저장하는 리스트
    private static List<Integer> oilQuantity = new ArrayList<>();
    // 각 열(column)에서 연결된 석유 지역 ID를 저장하는 리스트
    private static List<Set<Integer>> way = new ArrayList<>();
    // 현재 석유 지역의 ID를 추적 (2부터 시작)
    private static int oilIndex = 2;
    private static int m = 0; // land 배열의 열 개수
    private static int n = 0; // land 배열의 행 개수

    public int solution(int[][] land) {
        n = land.length;    // 행의 개수
        m = land[0].length; // 열의 개수

        // 0번과 1번 인덱스는 사용하지 않음 (편의상 0으로 초기화)
        oilQuantity.add(0); 
        oilQuantity.add(0);

        // 각 열에 대해 초기화
        for (int i = 0; i < m; i++) {
            way.add(new HashSet<>());
        }

        // 전체 land 배열을 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 석유 지역(값이 1)을 발견하면 BFS로 탐색
                if (land[i][j] == 1) {
                    oilQuantity.add(0); // 새로운 석유 지역에 대해 초기 석유 양 추가
                    checkSameOil(land, i, j); // BFS 탐색
                    oilIndex++; // 다음 석유 지역 ID로 이동
                }
            }
        }

        // 최대 석유량 계산
        int answer = 0;
        for (int i = 0; i < m; i++) {
            int sum = 0;
            Set<Integer> wayOil = way.get(i); // 열(column)에 연결된 석유 지역의 ID 집합
            for (int wayOilIndex : wayOil) {
                sum += oilQuantity.get(wayOilIndex); // 해당 석유 지역들의 석유 양 합산
            }
            answer = Math.max(sum, answer); // 최대값 갱신
        }

        return answer; // 최대 석유량 반환
    }

    // BFS 탐색으로 동일한 석유 지역을 식별
    private static void checkSameOil(int[][] land, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j}); // 시작 지점 큐에 추가

        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 현재 위치 꺼내기
            int x = current[0]; // 현재 행
            int y = current[1]; // 현재 열

            // 범위를 벗어나거나 이미 방문한 경우 무시
            if (x < 0 || x >= n || y < 0 || y >= m || land[x][y] != 1) {
                continue;
            }

            // 현재 위치를 현재 석유 지역 ID로 마킹
            land[x][y] = oilIndex;

            // 해당 석유 지역의 석유 양 증가
            oilQuantity.set(oilIndex, oilQuantity.get(oilIndex) + 1);

            // 현재 열에 해당 석유 지역 ID 추가
            way.get(y).add(oilIndex);

            // 4방향(상, 하, 좌, 우)으로 BFS 확장
            queue.add(new int[]{x - 1, y}); // 위쪽
            queue.add(new int[]{x + 1, y}); // 아래쪽
            queue.add(new int[]{x, y - 1}); // 왼쪽
            queue.add(new int[]{x, y + 1}); // 오른쪽
        }
    }
}