[Programmers] Lv 2. [PCCP 기출문제]2번]

문제 링크

---

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

프로그래머스

풀이

---

import java.util.*;

class Solution {
    // 방향 벡터 선언
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};

    public int solution(int[][] land) {
        int answer = 0;
        
				// 매 열마다 bfs를 돌린다.
        for(int i = 0; i < land[0].length; i++){
            int sum = 0;
            boolean[][] visited = new boolean[land.length][land[0].length];
            for(int j = 0; j < land.length; j++){
                sum += bfs(visited, land, j, i);
            }
            
            answer = Math.max(answer, sum);
        }
        
        return answer;
    }
    
    public static int bfs(boolean[][] visited, int[][] land, int r, int c){
        // 방문한 적 있거나, 석유가 없다면 메서드를 종료
        if(visited[r][c] || land[r][c] == 0) return 0;
        // 반환할 석유 매장량을 선언
        int total = 1;
        // 좌표 정보를 담을 큐를 선언
        Queue<int[]> queue = new LinkedList<>();
        // 시작점을 방문처리하고 큐에 넣음
        int[] start = new int[] {r, c};
        visited[r][c] = true;
        queue.offer(start);
        
        while(!queue.isEmpty()){
            // 큐에서 좌표 정보를 꺼낸다.
            int[] cur = queue.poll();
						// 방향벡터에 따라 bfs를 진행
            for(int i = 0; i < 4; i++){
								// 만약 배열 범위를 벗어났다면 다음 반복문 진행
                if(!check(cur[0]+dr[i], cur[1]+dc[i], land)) continue;
								// 방문한 적 없고, 석유가 매장되어 있다면
                if(!visited[cur[0]+dr[i]][cur[1]+dc[i]] && land[cur[0]+dr[i]][cur[1]+dc[i]] != 0){
                    // 총 매장량을 올린 뒤 방문처리 후 다시 큐에 넣는다.
										total++;
                    visited[cur[0]+dr[i]][cur[1]+dc[i]] = true;
                    int[] now = new int[] {cur[0]+dr[i], cur[1]+dc[i]};
                    queue.offer(now);
                }
            }
        }
        // 총 매장량 반환
        return total;
        
    }
    
		// 배열 범위 체크 함
    public static boolean check(int r, int c, int[][] land){
        return (r>= 0 && r < land.length && c>=0 && c <land[0].length);
    }
}

• 기본적인 문제의 컨셉은 BFS이다. “좌표”가 나오고, 그 좌표들이 이어져있는지를 확인하는 가장 간단하고 빠른 방법은 BFS 뿐이기 때문이다.
• 다만, 위의 방식으로 하면 매 반복문마다 새롭게 BFS를 돌리기 때문에, 정확성은 통과할지언정, 효율성에서 시간 초과가 나버린다.
• 따라서, BFS 횟수를 얼마나 줄일 수 있을지를 생각해야 한다.

import java.util.*;

class Solution {
    // 방향 벡터 선언
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};
    // 마크 배열 : 해당 석유가 '몇번째 석유 덩어리인지' 체크하기 위한 배열
    public static int[][] mark;
    // 마크 넘버 : 1부터 시작(0번은 석유가 아닌 곳)하여, 매 석유 덩어리를 찾을 때마다 늘어남
    public static int mark_num = 1;
    // map : 덩어리 번호와 매장량을 key-value로 저장하기 위함
    public static Map<Integer, Integer> map = new HashMap<>();
    

    public int solution(int[][] land) {
        int answer = 0;
        // mark를 land와 같은 크기의 배열을 선언
        mark = new int[land.length][land[0].length];
        // 전체적으로 bfs를 먼저 돌리기 위한 방문 배열 선언
        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++){
                // bfs 메서드
                bfs(visited, land, i, j);
            }
        }
        // bfs가 끝나면 mark엔 각 덩어리 번호가 입력되어 있다.
        // 따라서, 다시 열따라 반복문을 돌려서 최고 매장량을 찾아야 한다.
        for(int i = 0; i < land[0].length; i++){
            // 덩어리의 갯수와 동일한 방문배열 선언 : "그 덩어리를 이번 열에서 이미 시추했는지"
            boolean[] marked = new boolean[mark_num+1]; // +1해줘서 코드를 깔끔하게.
            // 이번 열에서의 시추량
            int sum = 0;
            for(int j = 0; j < land.length; j++){
                // 석유 덩어리가 매장되어 있고, 아직 그 덩어리를 방문한 적 없다면
                if(mark[j][i] != 0 && !marked[mark[j][i]]){
                    // 방문체크하고, 그 덩어리에 해당하는 매장량을 sum에 더해준다.
                    marked[mark[j][i]] = true;
                    sum += map.get(mark[j][i]);
                }
            }
            // answer은 그중 최고값
            answer = Math.max(sum, answer);
        }
        
        return answer;
    }
    
    
    public static void bfs(boolean[][] visited, int[][] land, int r, int c){
        // 방문한 적 있거나, 석유가 없다면 메서드를 종료한다.
        if(visited[r][c] || land[r][c] == 0) return;
        // 반환할 석유 매장량을 선언한다. 석유가 있음을 전제로 하므로 1부터 시작.
        int total = 1;
        // 좌표 정보를 담을 큐를 선언
        Queue<int[]> queue = new LinkedList<>();
        // 시작점을 방문처리하고 큐에 넣는다.
        int[] start = new int[] {r, c};
        visited[r][c] = true;
        mark[r][c] = mark_num;
        queue.offer(start);
        
        while(!queue.isEmpty()){
            // 큐에서 좌표를 꺼낸다.
            int[] cur = queue.poll();
            // 방향 벡터에 따라서 dfs 진행
            for(int i = 0; i < 4; i++){
                // check : 배열의 범위를 벗어난다면 다음 반복문으로
                if(!check(cur[0]+dr[i], cur[1]+dc[i], land)) continue;
                // 방문한 적이 없고, 매장량이 0이 아니라면
                if(!visited[cur[0]+dr[i]][cur[1]+dc[i]] && land[cur[0]+dr[i]][cur[1]+dc[i]] != 0){
                    // 총 매장량을 더해주고, 방문처리를 해준 뒤 큐에 넣어준다.
                    total++;
                    visited[cur[0]+dr[i]][cur[1]+dc[i]] = true;
                    int[] now = new int[] {cur[0]+dr[i], cur[1]+dc[i]};
                    queue.offer(now);
                    
                    // mark에 덩어리 번호를 표시해준다.
                    mark[cur[0]+dr[i]][cur[1]+dc[i]] = mark_num;
                }
            }
        }
        // 모든게 끝났으면 이번 덩어리에 해당하는 매장량을 map에 넣어주고, 다음 덩어리를 체크한다.
        map.put(mark_num++, total);
        
    }
    
    // 배열 범위를 나갔는지 안나갔는지 체크하는 함수
    public static boolean check(int r, int c, int[][] land){
        return (r>= 0 && r < land.length && c>=0 && c <land[0].length);
    }
}

• 기본적인 아이디어는, BFS를 처음 한번 돌린 뒤에 그 정보를 어딘가에 저장해놓는 것이다.
• “석유 덩어리”가 몇개인지를 세고. 각 점이 어느 석유 덩어리에 속하는지, 그리고 그 매장량은 얼마인지를 각각 배열과 맵에 저장한 뒤에 이를 응용하는 방법이다.
• Lv 2가 맞나 싶다. BFS를 떠올리긴 쉽지만 효율성 부분이 전혀 Lv 2 난이도가 아닌데…

import java.util.*;

class Solution {
    // 방향 벡터 선언
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};
    // 마크 배열 : 해당 열에 '얼마나 석유를 캘수 있는지' 체크하기 위한 배열
    public static int[] mark;
    

    public int solution(int[][] land) {
        int answer = 0;
        // mark를 land의 열과 같은 크기의 배열을 선언
        mark = new int[land[0].length];
        // 전체적으로 bfs를 먼저 돌리기 위한 방문 배열 선언
        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++){
                // bfs 메서드
                bfs(visited, land, i, j);
            }
        }
        // bfs가 끝나면 mark엔 열별 최고 매장량이 들어가 있따.
        for(int i = 0; i < mark.length; i++){
            // answer은 그중 최고값
            answer = Math.max(mark[i], answer);
        }
        
        return answer;
    }
    
    
    public static void bfs(boolean[][] visited, int[][] land, int r, int c){
        // 방문한 적 있거나, 석유가 없다면 메서드를 종료한다.
        if(visited[r][c] || land[r][c] == 0) return;
        // 반환할 석유 매장량을 선언한다. 석유가 있음을 전제로 하므로 1부터 시작.
        int total = 1;
        // 이번 bfs에서 덩어리가 차지하는 열의 정보를 담을 Set 선언
        Set<Integer> set = new HashSet<>();
        // 좌표 정보를 담을 큐를 선언
        Queue<int[]> queue = new LinkedList<>();
        // 시작점을 방문처리하고 큐에 넣는다.
        int[] start = new int[] {r, c};
        visited[r][c] = true;
        // 열 값을 set에 넣는다
        set.add(c);
        queue.offer(start);
        
        while(!queue.isEmpty()){
            // 큐에서 좌표를 꺼낸다.
            int[] cur = queue.poll();
            // 방향 벡터에 따라서 dfs 진행
            for(int i = 0; i < 4; i++){
                // check : 배열의 범위를 벗어난다면 다음 반복문으로
                if(!check(cur[0]+dr[i], cur[1]+dc[i], land)) continue;
                // 방문한 적이 없고, 매장량이 0이 아니라면
                if(!visited[cur[0]+dr[i]][cur[1]+dc[i]] && land[cur[0]+dr[i]][cur[1]+dc[i]] != 0){
                    // 총 매장량을 더해주고, 방문처리를 해준 뒤 큐에 넣어준다. 열값도 set에 넣는다.
                    total++;
                    set.add(cur[1]+dc[i]);
                    visited[cur[0]+dr[i]][cur[1]+dc[i]] = true;
                    int[] now = new int[] {cur[0]+dr[i], cur[1]+dc[i]};
                    queue.offer(now);
                    
                    // mark에 덩어리 번호를 표시해준다.
                }
            }
        }
        Iterator<Integer> iter = set.iterator(); // set을 Iterator 안에 담기
		while(iter.hasNext()) { // iterator에 다음 값이 있다면
			mark[iter.next()] += total;
		}
        
    }
    
    // 배열 범위를 나갔는지 안나갔는지 체크하는 함수
    public static boolean check(int r, int c, int[][] land){
        return (r>= 0 && r < land.length && c>=0 && c <land[0].length);
    }
}

• 위와 비슷한 아이디어지만, ‘각 덩어리가 몇번째 덩어리에 속하냐’가 아니라, ‘각 덩어리가 어떤 열에 속하냐’라는 아이디어에서 착안한 것이다.
• 위의 코드보다 한결 간결하고 코드도 빨라졌음을 알 수 있다. 매번 set을 다시 선언해야 하는게 좀 오버헤드가 들긴 할 것 같다. 밖에 맵하나 세워두고 map 값이 1번만 변하는지 아닌지를 boolean으로 체크하는게 좀더 나을지도? 어쨌든 통과했으니 다행이다.