Lv.2 [PCCP 기출문제] 2번 - 석유 시추

이번 문제는 프로그래머스사이트 내에서 진행하고 있는 코딩역량인증시험(PCCP)를 준비해보기 위해 PCCP 기출문제 중 Lv.2에 해당하는 문제를 풀어보았습니다. 아직은 제가 DFS와 BFS를 문제를 많이 풀어보지는 않았기에 조금 겁을 먹고 들어가긴 했지만, 다행히 많이 고생하지는 않고 계획한 로직대로 풀렸습니다😁 그러면 설명 들어가겠습니다

 

문제설명

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

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

출처 : 프로그래머스(그림 1)

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

출처 : 프로그래머스(그림 2)

시추관은 (그림 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

 

제한시간 안내

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

코드

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class 석유시추 {
  // 석유의 존재 유무를 확인하기 위해 (상, 하, 좌, 우)를 움직일 수 있음.
  private static final int[] dx = {-1, 1, 0, 0};
  private static final int[] dy = {0, 0, -1, 1};

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

  public static int solution(int[][] land) {
    int height = land.length;
    int width = land[0].length;

    int[][] oilLand = new int[height][width]; // 석유 현황을 보여줄 2차원배열
    Map<Integer, Integer> oilStorage = new HashMap<>(); // 석유의 양과 구역을 저장
    int numOfOilSection = 2; // 석유 구역 번호 (1은 석유 존재 유무를 나타내므로 2부터 시작)

    // 석유 구역 찾기
    for (int i = 0; i < height; i++) {
      for (int j = 0; j < width; j++) {
        if (land[i][j] == 1) {//만약 석유가 존재하면~
          int amount = dfs(land, oilLand, i, j, numOfOilSection);//석유 양 계산을 위해 깊이 우선 탐색 ㄱㄱ
          oilStorage.put(numOfOilSection, amount);//계산된 오일의 양을 각 구역 번호에 저장
          numOfOilSection++;//그 다음에 구역에 저장해주기 위해 번호++
        }
      }
    }

    // 각 열마다 최대 석유보유량 계산
    int maxOil = 0;
    for (int j = 0; j < width; j++) {//각열마다 조회하므로
      Set<Integer> oilSectionSet = new HashSet<>();
      int totalOil = 0;
      for (int i = 0; i < height; i++) {//시추관이 세로로 들어갈 경우 오일이 들어있는 구역 번호를 저장.
        if (oilLand[i][j] > 1) {
          oilSectionSet.add(oilLand[i][j]);
        }
      }
      for (int id : oilSectionSet) {//구역 별 오일 저장량 저장.
        totalOil += oilStorage.get(id);
      }
      maxOil = Math.max(maxOil, totalOil);
    }
    return maxOil;
  }
  private static int dfs(int[][] land, int[][] oilLand, int height, int weight, int oilId) {
    if (height < 0 || height >= land.length || weight < 0 || weight >= land[0].length || land[height][weight] != 1) {
      return 0;
    }

    land[height][weight] = oilId;//오일 구역 번호 정해주기
    oilLand[height][weight] = oilId;//오일 구역 번호 정해주기
    int amountOfOil = 1;

    for (int d = 0; d < 4; d++) {//인근에 붙어 있는 배열도 확인해주기
      int nx = height + dx[d];
      int ny = weight + dy[d];
      amountOfOil += dfs(land, oilLand, nx, ny, oilId);
    }
    return amountOfOil;
  }
}

문제 설명

1. 우선 석유현황을 따로 저장하기 위해 oilLand 2차원 배열과 각 구역에 해당되는 석유 양을 저장하기 위해 oilStorage라는 HashMap을 선언해주었습니다.
2. 그리고 dfs 메서드를 통해 석유가 존재하는 곳의 구역들을 2부터 시작하여 저장해주었습니다. 왜 2부터 시작이냐면, 이미 석유가 존재하는 곳은 1이기 때문에 이것과 비교해주기 위해 2부터로 설정하였습니다.
3. 그 다음 석유가 존재한다고 확인이 된 타일 주변의 타일에도 석유가 존재하는지 확인하기 위해 맨 위에 static final로 선언되어 있는 dx와 dy로 검증해주었습니다.
4. 그 과정을 통해 각 구역별로 저장되어 있는 석유의 양을 return해주고 그 값을 oilStorage에 저장해주었습니다.
5. 그리고 시추관이 가로가 아닌 세로로 들어가므로 가로열의 길이를 나타내는 width만큼 for문을 돌리고,  그 안에서 세로열의 길이를 나타내주는 height로 for문을 작성하여 이중 for문을 활용하였습니다.
6. 아까 2번 설명문에서 제가 1이 아닌 섹션 구역을 2부터 저장해주었기 때문에 배열의 값을 순회하며 1보다 큰 값이 있다면, oilSectionset에 구역 인덱스를 저장해주었습니다.
7. 마지막으로 구역의 오일값을 totalOil에 더하여 이전에 저장되었던 maxOil값과 비교하기 위해 Math 클래스의 메서드인 max를 활용해 비교해주었습니다.

문제 난이도 많이 어려운 정도는 아니었던 것 같고 저와 같이 아직 DFS와 BFS의 경험과 지식이 부족하셔도 recursive function을 활용하실 줄 안다면 쬐끔? 만 고생하시면 충분히 해낼 수 있으리라 생각됩니다.(실패하면 Error! 성공하면 혁명 아닙니까!🫡)

이상 글 마치겠습니다~

https://github.com/bottomsUp-99?tab=repositories

bottomsUp-99 - Overview