[프로그래머스][Java][Lv. 2] [PCCP 기출문제] 2번 / 석유 시추

문제 설명

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

 

---

 

제한 사항

 

---

 

입출력 예

 

---

 

풀이

import java.util.HashMap;
import java.util.ArrayList;

class Solution {
    private ArrayList<Node> checkedLandList = new ArrayList<>();
    
    public int solution(int[][] land) {
        HashMap<Integer, Node> landMap = new HashMap<>();
        int answer = 0;
        
        for (int n = 0; n < land.length; n++) {
            for (int m = 0; m < land[0].length; m++) {
                int mn = (n + 1) * 1000 + (m + 1);
                
                if (land[n][m] == 1) landMap.put(mn, new Node(mn));
            }
        }
        
        // 인접 석유 노드끼리 연결
        for (int n = 0; n < land.length; n++) {
            for (int m = 0; m < land[0].length; m++) {
                // 현재 Node에 석유가 없을 때
                if (land[n][m] == 0) continue;
                
                int mn = (n + 1) * 1000 + (m + 1);
                Node curLand = landMap.get(mn);
                
                // 상
                Node up = landMap.getOrDefault(mn - 1, null);
                if (up != null) {
                    curLand.getLinkedLandList().add(up);
                }
                // 하
                Node down = landMap.getOrDefault(mn + 1, null);
                if (down != null) {
                    curLand.getLinkedLandList().add(down);
                }
                // 좌
                Node left = landMap.getOrDefault(mn - 1000, null);
                if (left != null) {
                    curLand.getLinkedLandList().add(left);
                }
                // 우
                Node right = landMap.getOrDefault(mn + 1000, null);
                if (right != null) {
                    curLand.getLinkedLandList().add(right);
                }
            }
        }
        
        for (int m = 0; m < land[0].length; m++) {
            for (Node node : checkedLandList) node.setVisit(false);
            checkedLandList.clear();
            
            int one = 0;
            ArrayList<Node> linkedLandList = new ArrayList<>();
            for (int n = 0; n < land.length; n++) {
                // 현재 Node에 석유가 없을 때
                if (land[n][m] == 0) continue;
                
                int mn = (n + 1) * 1000 + (m + 1);
                Node curLand = landMap.get(mn);
                
                if (curLand.getLinkedLandList().size() == 0) one++;
                else linkedLandList.add(curLand);
            }
            bfs(linkedLandList);
            answer = Math.max(answer, checkedLandList.size() + one);
        }
        
        return answer;
    }
    
    private void bfs(ArrayList<Node> linkedLandList) {
        ArrayList<Node> nextLinkedLandList = new ArrayList<>();
        
        for (Node node : linkedLandList) {
            if (!node.getVisit()) {
                node.setVisit(true);
                nextLinkedLandList.addAll(node.getLinkedLandList());
                checkedLandList.add(node);
            }
        }
        if (nextLinkedLandList.size() != 0) bfs(nextLinkedLandList);
    }
    
    static class Node {
        private int mn;
        private boolean visit = false;
        private ArrayList<Node> linkedLandList = new ArrayList<>();
        
        public Node(int mn) {
            this.mn = mn;
        }
        
        public boolean getVisit() {
            return visit;
        }
        
        public ArrayList<Node> getLinkedLandList() {
            return linkedLandList;
        }
        
        public void setVisit(boolean visit) {
            this.visit = visit;
        }
    }
}

 

import java.util.Stack;

class Solution {
    Stack<Integer> result = new Stack<>();
    
    public int solution(int[][] land) {
        int answer = 0;
        
        for (int m = 0; m < land[0].length; m++) {
            clearResult(land);
            
            for (int n = 0; n < land.length; n++) {
                if (land[n][m] == -1 || land[n][m] == 0) continue;
                int curLand = (n + 1) * 1000 + m;
                Stack<Integer> temp = new Stack<>();
                
                land[n][m] = -1;
                result.push(curLand);
                temp.add(curLand);
                bfs(temp, land);
            }
            answer = Math.max(answer, result.size());
        }
        return answer;
    }
    
    private void bfs(Stack<Integer> current, int[][] land) {
        Stack<Integer> next = new Stack<>();
        
        while (!current.empty()) {
            int landMn = current.pop();
            int n = landMn / 1000 - 1;  // y
            int m = landMn % 1000;  // x
            int temp = 0;
            
            // 상
            int up = n - 1;
            if (0 <= up && land[up][m] == 1 && land[up][m] != -1) {
                land[up][m] = -1;
                temp = landMn - 1000;
                result.push(temp);
                next.push(temp);
            }
            // 하
            int down = n + 1;
            if (down < land.length && land[down][m] == 1 && land[down][m] != -1) {
                land[down][m] = -1;
                temp = landMn + 1000;
                result.push(temp);
                next.push(temp);
            }
            // 좌
            int left = m - 1;
            if (0 <= left && land[n][left] == 1 && land[n][left] != -1) {
                land[n][left] = -1;
                temp = landMn - 1;
                result.push(temp);
                next.push(temp);
            }
            // 우
            int right = m + 1;
            if (right < land[0].length && land[n][right] == 1 && land[n][right] != -1) {
                land[n][right] = -1;
                temp = landMn + 1;
                result.push(temp);
                next.push(temp);
            }
        }
        if (!next.empty()) bfs(next, land);
    }
    
    private void clearResult(int[][] land) {
        while (!result.empty()) {
            int landMn = result.pop();
            int y = landMn / 1000 - 1;  // n
            int x = landMn % 1000;  // m
            land[y][x] = 1;
        }
        result.clear();
    }
}

 

ㄴ 효율성 테스트 통과 못한 코드

 

import java.util.HashMap;
import java.util.HashSet;
import java.util.ArrayList;

class Solution {
    private int groupId = 2;
    private ArrayList<int[]> resultList = new ArrayList<>();
    
    public int solution(int[][] land) {
        HashMap<Integer, Integer> groupSizeMap = new HashMap<>();
        HashSet<Integer> groupIdSet = new HashSet<>();
        int answer = 0;
        
        for (int n = 0; n < land.length; n++) {
            for (int m = 0; m < land[0].length; m++) {
                if (land[n][m] != 1) continue;
                resultList.clear();
                
                ArrayList<int[]> newLandList = new ArrayList<>();
                int[] curLand = new int[] { m, n };
                land[curLand[1]][curLand[0]] = groupId;
                newLandList.add(curLand);
                resultList.add(curLand);
                
                bfs(newLandList, land);
                
                groupSizeMap.put(groupId++, resultList.size());
            }
        }
        
        for (int m = 0; m < land[0].length; m++) {
            int sum = 0;
            groupIdSet.clear();
            for (int n = 0; n < land.length; n++) {
                if (land[n][m] > 1) groupIdSet.add(land[n][m]);
            }
            for (Integer gId : groupIdSet) sum += groupSizeMap.get(gId);
            answer = Math.max(answer, sum);
        }
        return answer;
    }
    
    private void bfs(ArrayList<int[]> curLandList, int[][] land) {       
        ArrayList<int[]> nextLandList = new ArrayList<>();
        
        for (int[] curLand : curLandList) {
            int m = curLand[0];
            int n = curLand[1];
            
            // 상
            if (0 <= n - 1) {
                int[] up = new int[] { m, n - 1 };
                if (land[up[1]][up[0]] == 1) {
                    land[up[1]][up[0]] = groupId;
                    nextLandList.add(up);
                    resultList.add(up);
                }
            }
            // 하
            if (n + 1 < land.length) {
                int[] down = new int[] { m, n + 1 };
                if (land[down[1]][down[0]] == 1) {
                    land[down[1]][down[0]] = groupId;
                    nextLandList.add(down);
                    resultList.add(down);
                }
            }
            // 좌
            if (0 <= m - 1) {
                int[] left = new int[] { m - 1, n };
                if (land[left[1]][left[0]] == 1) {
                    land[left[1]][left[0]] = groupId;
                    nextLandList.add(left);
                    resultList.add(left);
                }
            }
            // 우
            if (m + 1 < land[0].length) {
                int[] right = new int[] { m + 1, n };
                if (land[right[1]][right[0]] == 1) {
                    land[right[1]][right[0]] = groupId;
                    nextLandList.add(right);
                    resultList.add(right);
                }
            }
        }
        if (nextLandList.size() != 0) bfs(nextLandList, land);
    }
}

 

ㄴ 모든 테스트 통과한 코드

 

---

 

후기

음... 어렵다;; 효율성 테스트만 없었으면 진작에 통과했을 문제인데 최적화를 해야 하는 바람에 많이 통과하지 못하고 말았다... 처음에는 단순히 무난하게 노드를 만들고 객체 그래프 탐색하는 방법으로 했는데 효율성 테스트에서 전부 실패해서 자료구조와 for문 도는 것이 문제인가 싶어 Stack으로 바꾸고 for문 순회도 줄였지만 실패... 이쯤 되면 접근 방식이 틀렸다고 생각해서 오랫동안 고민한 결과 굳이 따로 클래스를 만들 필요가 없었고, 순회도 m과 n을 모두 도는 것 두 번만 하면 됐었다. 그리고 이번에는 마지막 순회 로직에서 매번 체크하는 것이 아닌 처음 순회할 때 지정해 준 groupId를 가지고 있는 land를 그냥 Set에 때려 박고 그룹의 크기를 모두 더하는 식으로 구현했다. 이렇게 하니 통과... 많이 노력해야겠다