[Programmers / Level2] 250136. [PCCP 기출문제] 2번 / 석유 시추 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/250136
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/250136. [PCCP 기출문제] 2번 / 석유 시추

입출력 조건

입출력 예시

문제 이해

• bfs를 이용하여 최대로 석유를 시추할 수 있는 석유량을 반환하는 문제

알고리즘

풀이 시간 : 37분

1. N, M 전역변수 선언
2. Visited, arr, count, dx 및 dy, map 전역변수 선언
3. Solution
   a. N, M, visited, map, arr 초기화
   b. visited와 Map 조건 부여 및 bfs 진행
   c. 최종 결과값 answer는 Math.max를 통해 구하기
4. 별도 메서드 bfs : 큐를 이용해 구현

import java.util.*;

class Solution {
    
    static int N;
    static int M;
    
    static boolean[][] visited;
    static int[] arr;
    static int count;
    
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] map;
    
    static int answer;
    
    public int solution(int[][] land) {
        N = land[0].length;
        M = land.length;
        answer = 0;
        
        map = land;
        
        arr = new int[M];
        visited = new boolean[M][N];
        
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(visited[i][j] || map[i][j] == 0){
                    continue;
                }
                bfs(i, j);
            }
        }
        
        int answer = 0;
        for(int i=0; i<M; i++){
            answer = Math.max(answer, arr[i]);
        }
        
        return answer;
    }
    
    public static int bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        Set<Integer> set = new LinkedHashSet<>();
        
        
        q.offer(new int[]{x, y});
        visited[x][y] = true;
        int count = 1;
        
        
        while(!q.isEmpty()){
            int[] current = q.poll();
            set.add(current[0]);
            
            for(int i=0; i<4; i++){
                int cx = current[0] + dx[i];
                int cy = current[1] + dy[i];
                
                if(!(x>=0 && x<N && y>=0 && y<M) || map[x][y] == 0 || visited[x][y]){
                    continue;
                }
                visited[x][y] = true;
                count++;
                q.offer(new int[]{x, y});
            }
        }
        for(int current : set){
            arr[current] += count;
        }
        return count;
    }
    
}

오답체크

• 테스트 미통과 문제
  
  • M, N과 관련하여 설정을 뒤집어주어야 통과가 가능함.
  • 또한, nx와 ny에 대한 설정을 x,y로 잘못하여 발생한 문제로 보임.

//before
...       
        arr = new int[M];
        visited = new boolean[M][N];
        
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(visited[i][j] || map[i][j] == 0){
                    continue;
                }
                bfs(i, j);
            }
        }
...
            
            for(int i=0; i<4; i++){
                int cx = current[0] + dx[i];
                int cy = current[1] + dy[i];
                
                if(!(x>=0 && x<N && y>=0 && y<M) || map[x][y] == 0 || visited[x][y]){
                    continue;
                }
                visited[x][y] = true;
                count++;
                q.offer(new int[]{x, y});
            }
        }
        for(int current : set){
            arr[current] += count;
        }
        return count;
    }
    
}

//after        
...
        arr = new int[M];
        visited = new boolean[N][M];
        
        for(int j=0; j<M; j++){
            for(int i=0; i<N; i++){
                if(visited[i][j] || map[i][j] == 0){
                    continue;
                }
                bfs(i, j);
            }
        }
...

            
            for(int i=0; i<4; i++){
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                
                if(nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny] == 0 || visited[nx][ny]){
                    continue;
                }
                visited[nx][ny] = true;
                count++;
                q.offer(new int[]{nx, ny});
            }
        }
        for(int current : set){
            arr[current] += count;
        }
        return count;
    }
    
}

최종 풀이

풀이 시간 : 1시간 16분(첫 풀이 시간 포함)

1. N, M 전역변수 선언
2. Visited, arr, count, dx 및 dy, map 전역변수 선언
3. Solution
   a. N, M, visited, map, arr 초기화
   b. visited와 Map 조건 부여 및 bfs 진행
   c. 최종 결과값 answer는 Math.max를 통해 구하기
4. 별도 메서드 bfs : 큐를 이용해 구현

import java.util.*;

class Solution {
    
    static int N;
    static int M;
    
    static boolean[][] visited;
    static int[] arr;
    static int count;
    
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] map;
    
    static int answer;
    
    public int solution(int[][] land) {
        M = land[0].length;
        N = land.length;
        answer = 0;
        
        map = land;
        
        arr = new int[M];
        visited = new boolean[N][M];
        
        for(int j=0; j<M; j++){
            for(int i=0; i<N; i++){
                if(visited[i][j] || map[i][j] == 0){
                    continue;
                }
                bfs(i, j);
            }
        }
        
        int answer = 0;
        for(int i=0; i<M; i++){
            answer = Math.max(answer, arr[i]);
        }
        
        return answer;
    }
    
    public static int bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        Set<Integer> set = new LinkedHashSet<>();
        
        
        q.offer(new int[]{x, y});
        visited[x][y] = true;
        int count = 1;
        
        
        while(!q.isEmpty()){
            int[] current = q.poll();
            set.add(current[1]);
            
            for(int i=0; i<4; i++){
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                
                if(nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny] == 0 || visited[nx][ny]){
                    continue;
                }
                visited[nx][ny] = true;
                count++;
                q.offer(new int[]{nx, ny});
            }
        }
        for(int current : set){
            arr[current] += count;
        }
        return count;
    }
    
}

결과