[플머] PCCP 기출문제 2번 / 석유 시추 🧪

난이도 : Lv. 2

문제 링크

프로그래머스

문제 설명

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

제한 사항

1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500

1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
land[i][j]는 0 또는 1입니다.
land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

정확성 테스트 케이스 제한사항

1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100

구조화

모든 자리에서 석유 덩어리를 찾으려고 탐색하지 말고, Boolean 배열로 탐색이 끝난 자리는 체크 후 재탐색 방지

탐색한 자리의 열 정보를 Set에 저장

sum 배열: 각 열에서 시추 가능한 석유량 저장

sum 배열에서 해당 열의 자리에 탐색 후 석유량 ++
sum 배열의 최댓값 출력

오답 노트

각 자리마다 탐색하려고 boolean 배열 초기화하면 시간초과 뜸

소스 코드

/*
각 열마다 석유 덩어리와 각 덩어리 구하기
이 중 가장 큰 값 구하기
bfs
*/

import java.util.*;

class Solution {
    public static int n, m;
    public static int[] sum;
    public static int[][] map,
    way = {{0,1},{0,-1},{1,0},{-1,0}};
    public static boolean[][] v;
    public int solution(int[][] land) {
        int answer = 0;
        
        n = land.length;
        m = land[0].length;
        map = new int[n][m];
        sum = new int[m];
        v = new boolean[n][m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = land[i][j];
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (map[j][i]==1 && !v[j][i]) {
                    bfs(j, i);
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            answer = Math.max(answer, sum[i]);
        }
        
        return answer;
    }
    
    public static int bfs(int sx, int sy) {
        int cnt = 0;
        Queue<int[]> q = new LinkedList<>();
        Set<Integer> set = new TreeSet<>();
        q.offer(new int[] {sx, sy});
        v[sx][sy] = true;
        
        while (!q.isEmpty()) {
            int x = q.peek()[0];
            int y = q.peek()[1];
            q.poll();
            set.add(y);
            
            cnt++;
            
            for (int i = 0; i < 4; i++) {
                int nx = x + way[i][0];
                int ny = y + way[i][1];
                
                if (nx<0 || nx>=n || ny<0 || ny>=m || v[nx][ny] 
                    || map[nx][ny]==0) {
                    continue;
                }
                
                q.offer(new int[] {nx, ny});
                v[nx][ny] = true;
            }
        }
        
        for (Integer i : set) {
            sum[i] += cnt;
        }
        
        return cnt;
    }
}