https://school.programmers.co.kr/learn/courses/30/lessons/250136
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
최근에 PCCP를 JAVA 언어로 응시했다가 큰 충격을 받아 풀기 시작했다.
문제 설명
문제는 간단하다.
열 기준으로 막대기를 꽂았을 때 석유에 해당하는 블록을 만난다면 근처 오일들을 전부 합한 것만큼 시추하면된다.
(근처 오일의 판단 기준은 상하좌우로 맟닿아있는 것이며 대각선은 해당되지 않는다.)
중요한 점은 효율성이 평가 항목에 포함되어있다는 점이다.
풀이 계획
DFS & Memorization
1. DFS를 이용해 특정 지점이 석유라면 근처를 전부 돌아다니며 해당 석유의 덩어리 크기를 구해준다.
2. 구한 덩어리 크기만큼을 다시 돌면서 덩어리 안의 값들을 1이 아닌 석유 덩어리 크기로 저장해준다.
3. 덩어리들마다 index값을 활용해 시추를 할 때 중복된 덩어리들은 신경 안 쓰고 내려갈 수 있도록 한다.
풀이 과정
import java.util.*;
class Solution {
private static int N;
private static int M;
private static int[][] delta = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int solution(int[][] land) {
int answer = 0;
N = land.length;
M = land[0].length;
boolean[][] visited = new boolean[N][M];
int[][] updateVisited = new int[N][M];
int idx = 1;
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
if (!visited[r][c] && land[r][c] == 1) {
dfsUpdate(land, updateVisited, r, c, dfs(land, visited, r, c), idx++);
}
}
}
for (int c = 0; c < M; c++) {
boolean[] check = new boolean[idx];
int sum = 0;
for (int r = 0; r < N; r++){
if (land[r][c] > 0 && !check[updateVisited[r][c]]) {
sum += land[r][c];
check[updateVisited[r][c]] = true;
}
}
answer = Math.max(answer, sum);
}
return answer;
}
private static int dfs(int[][] land, boolean[][] visited, int r, int c) {
Deque<Info> stack = new ArrayDeque<>();
stack.push(new Info(r, c));
visited[r][c] = true;
int count = 1;
while(!stack.isEmpty()){
Info info = stack.pollLast();
r = info.r;
c = info.c;
for (int i = 0; i < 4; i++) {
int nr = r + delta[i][0];
int nc = c + delta[i][1];
if (isin(nr, nc) && !visited[nr][nc] && land[nr][nc] == 1) {
stack.push(new Info(nr, nc));
visited[nr][nc] = true;
count++;
}
}
}
return count;
}
private static void dfsUpdate(int[][] land, int[][] visited, int r, int c, int size, int idx) {
land[r][c] = size;
visited[r][c] = idx;
Deque<Info> stack = new ArrayDeque<>();
stack.push(new Info(r, c));
while(!stack.isEmpty()){
Info info = stack.pollLast();
r = info.r;
c = info.c;
for (int i = 0; i < 4; i++) {
int nr = r + delta[i][0];
int nc = c + delta[i][1];
if (isin(nr, nc) && visited[nr][nc] == 0 && land[nr][nc] != 0) {
land[nr][nc] = size;
visited[nr][nc] = idx;
stack.push(new Info(nr, nc));
}
}
}
}
private static boolean isin(int r, int c) {
return r >= 0 && r < N && c >= 0 && c < M;
}
private static class Info{
int r;
int c;
public Info(int r, int c) {
this.r = r;
this.c = c;
}
}
}
주석이 없어 일일히 설명하자면
DFS 문제 풀이를 위한 방향을 설정할 delta, 배열 크기를 담을 N, M, 그리고 배열 밖으로 나가 ArrayIndexOutOfBound를 보지 않게 해줄 isIn 함수를 작성해준다.
이후, 계획을 세웠던 것처럼 전체 배열을 돌면서 각 지점에서 dfs를 두 번 들어가준다. 한 번은 전체 덩어리 크기 탐지용, 한 번은 탐지된 크기를 바탕으로 업데이트 용도.
그것만 마무리 하면 열마다 시추를 꽂아보면서 확인하면 된다.
