[프로그래머스] 석유 시추 (Java)

링크

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

프로그래머스

 

주의점

탐색할 때마다 MAX 값을 구하는 연산을 하면, 효율성 측면에서 매우 불리해진다.

 

알고리즘 선택과 근거

• DFS
  • 최단 거리를 구하는 문제가 아니다. 그래서 BFS 는 고려하지 않았음
  • MAX 값을 구하는 게 중요하다.
• 메모이제이션
  • 탐색 할 때마다 MAX 값을 구한다고 하면, 효율성 측면에서 매우 불리해진다.
  • 석유 탐색
    • 석유 덩어리를 하나의 Team 이라고 정의하고 DFS 돌릴 때 Team 배열에 해당 Team 석유 매장량을 저장한다.
  • 석유 시추
    • 팀 방문을 확인할 1차원 배열을 초기화해준다.
    • 배열 탐색하면서 석유이며 팀에 방문 했나 안 했나로 판별 후 방문 안했으면 Sum 에 합산한다.
  • 결국 메모이제이션을 쓰면 불필요한 재연산을 줄일 수 있다.

 

정답 코드

import java.util.*;

class Solution {
    
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static boolean[][] visited;
    static int[][] team;
    static ArrayList<Integer> teamScore = new ArrayList<>();
    static int xSize, ySize;
    
    
    public int solution(int[][] land) {
        xSize = land.length;
        ySize = land[0].length;
        visited = new boolean[xSize][ySize];
        team = new int[xSize][ySize];
        int teamNumber = 1;
        
        // 석유 레이더 가동
        for (int i = 0; i < xSize; i++) {
            for (int j = 0; j < ySize; j++) {
                if (!visited[i][j] && land[i][j] == 1) {
                    teamScore.add(dfs(1, i, j, land, teamNumber));
                    teamNumber++;
                }
            }
        }
        
        int answer = 0;
        
        // 석유 시추 시작!
        for (int i = 0; i < ySize; i++) {
            int sum = 0;
            boolean[] check = new boolean[teamNumber];
            for (int j = 0; j < xSize; j++) {
                int t = team[j][i];
                if (t != 0 && !check[t]) {
                    sum += teamScore.get(t - 1);
                    check[t] = true;
                    continue;
                }
            }
            answer = Math.max(answer, sum);
        }
        
        return answer;
    }
    
    public int dfs(int cnt, int x, int y, int[][] land, int teamNumber) {
        
        team[x][y] = teamNumber;
        visited[x][y] = true;
        
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            
            if (nx < 0 || ny < 0 || nx >= xSize || ny >= ySize) {
                continue;
            }
            
            if (visited[nx][ny] || land[nx][ny] == 0) {
                continue;
            }
            
            cnt = dfs(cnt + 1, nx, ny, land, teamNumber);
        }
        
        
        return cnt;
    }
}

 

위 코드 맘에 안들어서 한번 짧게 리팩토링해봤는데

 

import java.util.*;

class Solution {
    
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static boolean[][] visited;
    static int[][] team;
    static ArrayList<Integer> teamScore = new ArrayList<>();
    static int xSize, ySize;
    
    
    public int solution(int[][] land) {
        xSize = land.length;
        ySize = land[0].length;
        visited = new boolean[xSize][ySize];
        team = new int[xSize][ySize];
        int teamNumber = 1;
        int answer = 0;
        
        for (int i = 0; i < ySize; i++) {
            int sum = 0;
            Set<Integer> check = new HashSet<>();
            
            for (int j = 0; j < xSize; j++) {
                
                if (team[j][i] != 0 && !check.contains(team[j][i])) {
                    sum += teamScore.get(team[j][i] - 1);
                    check.add(team[j][i]);
                    continue;
                }
                
                if (!visited[j][i] && land[j][i] == 1) {
                    int tmp = dfs(1, j, i, land, teamNumber);
                    teamScore.add(tmp);
                    sum += tmp;
                    check.add(teamNumber);
                    teamNumber++;
                }
            }
            
            answer = Math.max(answer, sum);
        }
        
        return answer;
    }
    
    public int dfs(int cnt, int x, int y, int[][] land, int teamNumber) {
        
        team[x][y] = teamNumber;
        visited[x][y] = true;
        
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            
            if (nx < 0 || ny < 0 || nx >= xSize || ny >= ySize) {
                continue;
            }
            
            if (visited[nx][ny] || land[nx][ny] == 0) {
                continue;
            }
            
            cnt = dfs(cnt + 1, nx, ny, land, teamNumber);
        }
        
        
        return cnt;
    }
}

 

더 느림 ㅎㅎ.. ㅠ