[BFS] 석유 시츄

❓문제

시추관을 수직으로 하나만 뚫을 수 있음. 여러 덩어리의 석유를 시추관이 지나가면 그 합을 시추할 수 있음.

시추할 수 있는 석유의 최대양을 리턴.

---

🖐️손코딩

bfs(start: 석유가 있는 칸):
	queue.offer(석유 있는 칸의 좌표)
    while(queue가 비어있지 않을 때)
    	curx: 현재 x값 cury : 현재 y값
        덩어리 + 1
        cols.add(cury) : 덩어리가 있는 칸의 y값(시추관이 y값만 신경쓸거임!)
        for(상하 좌우):
        	1. 격자 볌위 밖이면 패스
            2. 이미 방문했으면 패스
            3. 석유 없으면 패스
            
            queue.offer(다음 석유 칸)
            
main:
	for(i: 0~n-1 & j: 0~m-1)
    	if(방문하지 않은 칸 + 석유가 있는 칸)
        	size = 0
            cols = new HashSet<>();
            bfs(i,j)
            answerarr[열] +=size
     return answerarr중 최대값

---

👩‍💻구현 코드

 

import java.util.*;

class Solution {
    int n, m;
    int[] dx = {-1,1,0,0};
    int[] dy = {0, 0, -1, 1};
    HashSet<Integer> cols;
    boolean[][] visited;
    int size;
    
    private void bfs(int startx, int starty, int[][] land){
        Queue<int[]> queue = new LinkedList<>();
        visited[starty][startx] = true;
        queue.offer(new int[]{starty, startx});
        
        while(!queue.isEmpty()){
            int[] info = queue.poll();
            int cury = info[0];
            int curx = info[1];
            size++;
            cols.add(curx);
            
            for(int i = 0; i<4; i++){
                int ny = cury + dy[i];
                int nx = curx + dx[i];
                
                if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if(visited[ny][nx]) continue;
                if(land[ny][nx] == 0) continue;
                
                visited[ny][nx] = true;
                queue.offer(new int[]{ny, nx});
            }
        }
    }
    
    public int solution(int[][] land) {
        n = land.length; // y
        m = land[0].length; // x
        visited = new boolean[n][m];
        int[] answerarr = new int[m];
        int answer = 0;
        
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                if(!visited[i][j] && land[i][j] == 1){
                    size=0;
                    cols = new HashSet<>();
                    bfs(j, i, land);
                    for(int col : cols){
                        answerarr[col] += size;
                    }
                }
            }
        }
        
        Arrays.sort(answerarr);
        answer = answerarr[m-1];
        return answer;
    }
}

 

HashMap vs HashSet

1. HashSet (값만 들어있는 주머니)
HashSet은 단일 값만 모아둔 집합이라 원소를 하나씩 꺼내서 쓸 수 있음.

HashSet<Integer> cols = new HashSet<>();

for (int col : cols) {
    // col에 0, 1, 2... 같은 숫자 값이 하나씩 들어옴!
}

2. HashMap (Key-Value 쌍으로 된 사전)
어떤 걸 기준으로 순회할지 명시해줘야함

1) value들만 꺼내서 순회할 떄
Map<String, Integer> map = new HashMap<>();

for (int val : map.values()) {
    // val에 Map에 들어있는 '값(Value)'들만 하나씩 꺼내짐!
}

2) Key 기준으로 순회할때
for (String key : map.keySet()) {
    int val = map.get(key); // Key로 Value를 조회!
}

3. TreeMap (Key를 기준으로 오름차순)
내림차순으로 바꾸고 싶다면?
Map<Integer, String> map = new TreeMap<>(Collections.reverseOrder());
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");

for (int key : map.keySet()) {
    System.out.print(key + " "); // 출력: 3 2 1 (내림차순 정렬)
}

---

 

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

프로그래머스