[알고리즘] 프로그래머스 2단계 - [PCCP 기출문제] 2번 / 석유 시추

프로그래머스 문제 링크

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

 

문제 설명

2차배열로 주어진 lands라는 땅이라는 배열 값에서 석유 시추를 직선으로 내려서 시추관과 석유가 닫는 모든 석유의 양이 최대인 경우를 찾는다.

석유는 숫자 1로 되어있다.

 

예시

lands

 [[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]]

 

result

9

 

일반적인 미로찾기나 섬찾기에서 사용하는 bfs 방식으로 풀었다고 생각했는데 효율성에서 시간초과가 발생한다..

일단 해결해보고 해결이 안되면 GPT에 최적화를 받아봐야겠다.

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {

	// 좌, 우
    static int[] dx = {1, -1, 0, 0};
	
    // 상, 하
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solution(new int[][]{
                {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}
        }));
    }

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

        int n = land[0].length;

        int m = land.length;

        int maxCnt = 0;

        for (int i = 0; i < n; i++) {
            maxCnt = Math.max(bfs(land, i, n, m), maxCnt);
        }

        return maxCnt;
    }

	// 세로로 너비 탐색
    private int bfs(int[][] land, int index, int n, int m) {
        int cnt = 0;

        boolean[][] visited = new boolean[m][n];

        // 세로로 이동
        for (int i = 0; i < land.length; i++) {

            // 세로로 내려가면서 1여부 체크
            if (land[i][index] != 1 || visited[i][index]) {
                continue;
            }

            // 현재 y값에서 스택 생성
            ArrayDeque<int[]> deque = new ArrayDeque<>();

            // x , y
            deque.add(new int[]{index, i});
			
            // 처음 1인 경우를 찾아기에 cnt 1 추가
            cnt++;
			
            // 방문 여부
            visited[i][index] = true;

            while (!deque.isEmpty()) {

                // 현재 위치
                int[] curPos = deque.pop();

                for (int j = 0; j < 4; j++) {
                    int curX = dx[j] + curPos[0];
                    int curY = dy[j] + curPos[1];

                    if (curX >= 0 && curX < n && curY >= 0 && curY < m && !visited[curY][curX] && land[curY][curX] == 1) {
                        deque.add(new int[]{curX, curY});
                        visited[curY][curX] = true;
                        cnt++;
                    }
                }
            }
        }

        return cnt;
    }
}