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

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

프로그래머스

 

내가 푼 풀이

[정리]

• DFS를 이용하여 인접한 석유들의 size를 구하고 oil변수에 column별 시추할 수 있는 석유의 양을 더해서 저장한다.
• DFS가 아닌 BFS를 사용해도 된다.
• 제일 시간을 많이 들인 부분
  • maxC를 해서 최대 column을 계산하고 넣는건 했는데 minC 계산하는걸 빼먹어서 계속 오답이 나왔다.

import java.util.*;

class Position{
    int r=-1, c=-1;
    public Position(){}
    public Position(int r,int c){this.r = r; this.c = c;}
}

class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        int[] oil = new int[land[0].length];
        boolean[][] visited = new boolean[land.length][land[0].length];
        
        for(int i = 0; i < land.length; i++){
            for(int j = 0; j < land[0].length; j++){
                if(visited[i][j])   continue;

                if(land[i][j]==0)  visited[i][j] = true;
                else {
                    int size = 0;
                    int maxC = j;
                    int minC = j;
                    
                    // DFS
                    Stack<Position> stack = new Stack<>();
                    stack.push(new Position(i,j));
                    
                    while(!stack.isEmpty()){
                        Position curr  = stack.pop();
                        if(visited[curr.r][curr.c]) continue;
                        visited[curr.r][curr.c] = true;
                        
                        if(land[curr.r][curr.c] == 1){
                            size++;
                            maxC = Math.max(maxC, curr.c);
                            minC = Math.min(minC, curr.c);
                            if(curr.r-1 >= 0)                stack.push(new Position(curr.r-1,curr.c));
                            if(curr.r+1 < land.length)       stack.push(new Position(curr.r+1,curr.c));
                            if(curr.c-1 >= 0)                stack.push(new Position(curr.r,curr.c-1));
                            if(curr.c+1 < land[0].length)    stack.push(new Position(curr.r,curr.c+1));
                        }
                        
                    }
                    for(int k = minC; k <= maxC; k++){
                        oil[k] += size;

                    }
                }

            }
        }
        
        for(int o: oil){
            answer = Math.max(answer, o);
        }
        
        return answer;
    }
    
    
}

 

! 심심할 때 혹은 나중에 복습할 겸 BFS로 풀어도 될 것 같다. 뭐, 사실상 stack을 queue로 바꾸기만 하면 되긴 하지만...