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

 

시간초과를 해결하고 너무너무너무 기뻐서 새로 글을 쓴다

아직 하나 남았지만,,

 

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

프로그래머스

 

import java.util.*;

class Solution {
    
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int result;
    static int[] resultArray;
    
    static HashSet<Integer> set = new HashSet<>(); // 포함된 열 저장
    static Map<Integer, Integer> map = new HashMap<>(); // 결과 저장
    
    public int solution(int[][] land) {
        int answer = 0;
        resultArray = new int[land[0].length];
        
        for(int i = 0; i < land.length; i++) {
            for(int j = 0; j < land[0].length; j++) {
                if(land[i][j] == 1) {
                    result = 1;
                    dfs(i, j, land);
                
                    Iterator<Integer> iter = set.iterator();
                    while(iter.hasNext()) {
                        // System.out.println(iter.next());
                        Integer n = iter.next();
                        map.put(n, map.getOrDefault(n, 0) + result);
                        // System.out.println(map);
                    }
                    
                    set.clear();
                    
                }   
            }
        }
        
        
        for(int i = 0; i< resultArray.length; i++) {
            answer = Math.max(answer, resultArray[i]);
        }
        
        answer = Collections.max(map.values());
        
        
        return answer;
        
    }
    
    void dfs(int x, int y, int[][] land) {
        land[x][y] = 0;
        set.add(y);
                
        for(int i = 0; i < 4; i++){
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            
            if(nextX >= 0 && nextX < land.length && nextY >=0 && nextY < land[0].length) {
                if(land[nextX][nextY] == 1) {
                    result++;
                    dfs(nextX, nextY, land);
                }
            }
                    
        }

    }
    
}

 

중복된 구간들을 가진 열을 건너뛰려고 HashMap을 사용해서 해보니 갑자기 이 방법이 떠올랐고 바꿔봤다 왜 이 방법이 이제야 떠올랐을까🤧🤧🤧🤧

 

전체를 돌다가 1이 나오면 그거와 연결된 구간들을 dfs를 통해 모두 더해주고 그 구간들에 속한 열을 HashSet에 담아주었다(중복을 걸러주기 위해 Set을 이용함)

그리고 HashMap을 이용해 "key:열 / value:결과값을 계속 합한 값" 을 넣어주고 이 중 최고값을 리턴했다

 

시간초과 다 해결됐는데 하나가 런타임에러뜬다 뭘까ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ

당장 몇시간뒤에 있을 수업이 너무나 걱정되지만 해결하고 자고싶다

 

 

⭐⭐

찾아보니까 DFS의 경우 모든 경로를 깊게 파고들어가며 탐색하기 때문에 깊이가 깊으면 스택 오버플로우(런타임에러)가 발생할 수 있다고 함

→ BFS로 바꿔봐야겠다!!!

 

 

]