[자바] 프로그래머스 - 석유 시추 ([PCCP 기출문제] 2번) (Lv2, Java)

목차

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

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘

• 탐색 (BFS, DFS 등)
  
  • 약간의 아이디어만 있다면 탐색 알고리즘으로 풀 수 있다.

 

풀이

  우리가 알아야 하는건, 각 열 번호에서 접근 가능한 석유들의 합이다. cnt[X] 라는 배열을 정의해보자. 이건 X 인덱스 열에서 접근 가능한 석유들의 총 합을 뜻한다. 최종적으로 cnt[0] 부터 cnt[m-1] 까지의 값 중 가장 큰 값을 출력하면 될 것이다.

 

  예를들어 아래와 같이 표현될 것이다. 최종적으로 cnt 배열에서 가장 큰 값이 9 이므로 9가 답이다.

 

---

 

  그럼 이제 cnt[] 에 값을 어떻게 채울 수 있을지 생각해보자.

서로 떨어진 각 석유들의 그룹을 생각해보자. 예를들어 이하 그림에서 색깔 다른게 서로 다른 그룹이다.

 

 

 

  해당 석유 그룹의 총 양과, 해당 석유 그룹이 영향을 끼치는 열 인덱스를 어떻게든 알 수 있다고 해보자.

전자를 area, 후자를 candidates 라고 표현하였다. 그럼 아래처럼 알 수 있을꺼다.

 

 

 

  그렇다면, 각 그룹에 대해, candidates 번호들을 X에 넣어주면서 cnt[X] += area 를 해주면 cnt 배열을 얻을 수 있을꺼다.

아래처럼 진행될 것이다.

 

1. 회색 그룹 확인 후

 

 

2. 주황색 그룹 확인 후

 

3. 파란 그룹 확인 후

 

 

---

 

 

  여기까지 이해됬다면, 이제 알아야 하는건 저 area랑 candidates를 어떻게 구하는지만 알면 된다.

우선 area는 간단하다. "아직 살펴보지 않은 석유 그룹을 만났다면, BFS나 DFS를 돌리면서 몇 칸 전진이 가능한지 보면 된다.". 그리고 candidates도 마찬가지다 "area를 구하면서 만난 열 인덱스를 전부 set 같은데 넣어버리면 된다.". 어차피 set은 중복이 안되므로, 중복되서 들어갔더라도 하나만 남을꺼다 (아니면 BFS나 DFS 진행하면서 만난 최소 열 인덱스와 최대 열 인덱스만 남겨둬도 상관없다.)

...
int nr = cr+a;	// 다음 확인할 인접한 행 인덱스
int nc = cc+b;	// 다음 확인할 인접한 열 인덱스
if (nr<0||nr>=r||nc<0||nc>=c||land[nr][nc]==0) continue;
// 배열 범위를 넘어가거나, 석유가 없는 곳이라면 무시한다.

area++;	// 무지성으로 area는 증가시켜주면 된다.
land[nr][nc] = 0;	// 이미 본 석유는 없애자. 파라미터로 들어온걸 변경하지 않고싶다면 방문체크 배열을 따로 쓰면 된다.
candidates.add(nc);	// set을 썼으므로 그냥 nc를 무지성으로 넣어도 중복된건 알아서 제거된다.
q.add(new int[]{nr, nc});	// BFS 계속 진행

...

 

 

  참고로 해당 그룹 전체 탐색만 되면 되니 BFS, DFS는 상관 없다. 그냥 아무 탐색 알고리즘을 쓰면 된다. 각 그룹에 대한 탐색이 끝났다면, candidates에 포함된 각 열 인덱스에 area를 바로바로 더해주면 된다!

for (int candidate : candidates) {
    cnt[candidate] += area;
}

 

 

  최종적으로 cnt 배열에서 가장 큰 숫자가 답이다.

int max = 0;
for (int i = 0; i < cnt.length; i++) {
    if (cnt[i] > max) max = cnt[i];
}
return max;

 

 

코드 : github

import java.util.*;

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int solution(int[][] land) {
        int r = land.length;
        int c = land[0].length;

        int[] cnt = new int[c];

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (land[i][j] == 0) continue;

                Set<Integer> candidates = new HashSet<>();
                Queue<int[]> q = new ArrayDeque<>();
                q.add(new int[]{i, j});
                int area = 1;
                land[i][j] = 0;
                candidates.add(j);

                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    int cr = cur[0];
                    int cc = cur[1];

                    for (int a = -1; a <= 1; a++) {
                        for (int b = -1; b <= 1; b++) {
                            if (((a^b)&1)!=1) continue;

                            int nr = cr+a;
                            int nc = cc+b;
                            if (nr<0||nr>=r||nc<0||nc>=c||land[nr][nc]==0) continue;

                            area++;
                            land[nr][nc] = 0;
                            candidates.add(nc);
                            q.add(new int[]{nr, nc});
                        }
                    }
                }

                for (int candidate : candidates) {
                    cnt[candidate] += area;
                }
            }
        }

        int max = 0;
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] > max) max = cnt[i];
        }
        return max;
    }
}