석유 시추

1. 문제

코딩테스트 연습 - [PCCP 기출문제] 2번 / 석유 시추 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

2. 설명

기본은 BFS 알고리즘을 통해 인접한 석유들을 구하면 된다.

거기에 열마다 접근할 수 있는 석유의 총량을 저장하는 리스트 하나만 저장하면 된다.

 

예제 1

 

먼저 BFS 알고리즘 적용을 위해서 visited와 queue를 사용했다.

BFS의 알고리즘을 잘 모른다면 아래 글을 참조하면 된다.

 

너비 우선 탐색 (Breadth-First Search) (tistory.com)

너비 우선 탐색 (Breadth-First Search)

 

1. 각 칸마다 조회할 수 있는 반복문을 작성하여 방문하지 않았고 석유가 존재한다면 탐색 진행한다.
2. 상하좌우의 값을 탐색한다.
   열을 기준으로 값을 찾기 때문에 열이 중복되지 않게 Set에 열을 저장한다.
3. 상하좌우에 석유가 존재하고 방문하지 않았다면 방문 처리와 석유량을 증가시키고, 큐에 넣어 석유가 존재하는 칸에서 다시 탐색을 진행 할 수 있게 해준다.
4. 반복문이 끝났다면 열을 저장한 리스트에서 가장 큰 값을 찾아 반환한다.

 

3. 코드

public class Oil {
    static int n, m;            //세로,  가로
    static int[] oil;           //각 세로열에서 뽑을 수 있는 오일량
    static boolean[][] visited; //각 세로열에서 뽑을 수 있는 오일량

    public static void main(String[] args){
        int[][] land = {{0, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 1, 0, 0}, {1, 1, 0, 0, 0, 1, 1, 0}, {1, 1, 1, 0, 0, 0, 0, 0}, {1, 1, 1, 0, 0, 0, 1, 1}};

        System.out.println(solution(land));
    }

    public static int solution(int[][] land) {
        int answer = 0;

        n = land.length;
        m = land[0].length;
        oil = new int[m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++){
            for (int j =0; j < m; j++){
                if(land[i][j] == 1 && !visited[i][j]) bfs(land, i, j);
            }
        }

        answer = Arrays.stream(oil).max().getAsInt();

        return answer;
    }

    private static void bfs(int[][] land, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        visited[i][j] = true;
        
        //solution의 if문에서 이미 석유를 발견했으므로 1로 시작
        int count = 1;
        //같은 열의 중복 방지용 y값 체크
        Set<Integer> set = new HashSet<>();

        int[] xMove = {-1, 1, 0, 0};    //좌, 우
        int[] yMove = {0, 0, -1, 1};    //상, 하

        while(!queue.isEmpty()){
            int[] point = queue.poll();
            //현재 좌표의 y값 입력
            set.add(point[1]);

            //근처에 석유가 있나 체크
            for (int z = 0; z < 4; z++){
                int tempX = point[0] + xMove[z];
                int tempY = point[1] + yMove[z];

                //지도를 벗어나면 스킵
                if(tempX < 0 || tempY < 0 || tempX >= n || tempY >= m) continue;
                
                //석유가 있고 방문하지 않은 땅이면 큐에 삽입하여 탐색하게 하고
                //방문 처리 및 석유량 증가
                if(land[tempX][tempY] == 1 && !visited[tempX][tempY]){
                    queue.add(new int[]{tempX, tempY});
                    visited[tempX][tempY] = true;
                    count++;
                }
            }
        }

        for (Integer each : set) {
            oil[each] += count;
        }
    }
}