[프로그래머스/Level2] 석유 시추 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• BFS

필요 자료구조
- 시추관 위치(열) 별 석유량 저장용 배열
- BFS에서 석유 덩어리의 열 위치 저장용 Set (중복 제거 위해)

 

 

격자를 돌면서 방문하지 않은 1인 칸의 위치에서 BFS를 수행한다.

  - 석유 덩어리의 열 위치 저장용 Set을 활용한다.

  - 방문하지 않은 1인 칸을 방문하며, 해당 열의 위치를 Set에 저장하고, 석유 덩어리 개수를 구한다.

  - Set에 저장된 열 위치들에 현재 위치에서 구한 석유량을 누적해 더한다.

 

 

 

💥 유의사항

land 배열을 그대로 사용하면 틀린다. land 배열을 복사해 사용해야 정답이 된다,,

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int n,m;
    static int[][] map;
    static int[] oil;   // 시추관 위치별 석유량
    
    static boolean[][] visited;
    static int answer = 0;
    
    public int solution(int[][] land) {        
        n = land.length;
        m = land[0].length;
        
        map = land;
        visited = new boolean[n][m];
        oil = new int[m];        
        
        for(int i = 0 ; i < m ; i++) {
            for(int j = 0 ; j < n ; j++) {
                if(land[j][i] == 1 && !visited[j][i]) {
                    bfs(j, i);
                }
            }
        }
        
        for(int o : oil) {
            answer = Math.max(answer, o);
        }        
        return answer;
    }
    
    private static int bfs(int x, int y) {
        Set<Integer> set = new HashSet<>(); // 🔔 석유 덩어리의 열 위치 저장용 Set 🔔
        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        
        visited[x][y] = true;
        
        int tmpCnt = 1; // 석유 덩어리 개수
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            set.add(now[1]);    // 열 위치 저장
 
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(!inRange(nx, ny) || map[nx][ny] == 0 || visited[nx][ny])    continue;
                
                visited[nx][ny] = true;
                q.add(new int[] {nx, ny});
                tmpCnt++;
            }
        }
        
        // 열 위치에 석유량 저장
        for(int s : set) {
            oil[s] += tmpCnt;
        }
        
        return tmpCnt;
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < n && 0 <= y && y < m);
    }
}

 

 

➕ 다른 풀이 방식

- Map 사용한 풀이

[Programmers-Java] 석유 시추

 

 

---

💦 어려웠던 점

- 탐색할 때 n과 m의 크기를 설정할 때 잠시 헷갈려서 인덱스가 맞지 않는 이슈가 있었다,,

 

 

🧐 새로 알게 된 내용

 - 열 위치를 Set에 저장하고, 해당 배열의 인덱스에 누적해 저장하는 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

[코딩테스트/프로그래머스] 석유 시추(Java)