코테 연습 (프로그래머스) - 석유 시츄 ArrayDeque, Set

문제설명

제한사항

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
효율성 테스트 케이스 제한사항
주어진 조건 외 추가 제한사항 없습니다.

입출력 예

입출력 예 설명

풀이 설명

다른 사람의 풀이

import java.util.*;
class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};
        boolean[][] v = new boolean[land.length][land[0].length];
        int flag = 2;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<land.length;i++) {
            for(int j=0;j<land[i].length;j++) {
                if(land[i][j] != 1) continue;
                int cnt = 1;
                v[i][j] = true;
                ArrayDeque<int[]> q = new ArrayDeque<>();
                q.offer(new int[]{i,j});
                land[i][j] = flag;
                while(!q.isEmpty()) {
                    int[] cur = q.poll();
                    for(int d=0;d<4;d++) {
                        int nx = cur[0] + dx[d];
                        int ny = cur[1] + dy[d];
                        if(nx<0||nx>land.length-1||ny<0||ny>land[0].length-1||v[nx][ny]||land[nx][ny]!=1) continue;
                        v[nx][ny] = true;
                        land[nx][ny] = flag;
                        cnt++;
                        q.offer(new int[]{nx,ny});
                    }
                }
                map.put(flag, cnt);
                flag++;
            }
        }

        for(int i=0;i<land[0].length;i++) {
            Set<Integer> set = new HashSet<>();
            for(int j=0;j<land.length;j++) {
                if(land[j][i] > 1) set.add(land[j][i]);
            }
            int sum = 0;
            for(Integer a : set) sum += map.get(a);
            answer = Math.max(answer, sum);
        }
        return answer;
    }
}

제가 참고한 풀이방법입니다. 심플하게 하나로 할 수 있는 방식인데 이해하기도 수월하였고 좋은 코드라고 생각합니다.

dx, dy는 방향을 나타내는 배열이고,
v 는 방문 여부를 나타내는 이중 배열입니다.
flag는 방문하였을 경우 값을 변경시켜줄 변수입니다.

이중 포문으로 값을 시추하는 한블록의 위치를 정해줍니다.
만약 1이 이라면, 기름의 개수를 담은 cnt를 1로 정해주고,

ArrayDeque<int[]> q = new ArrayDeque<>(); 를 선언합니다.

ArrayDeque<int[]> 는 선입 선출 방식의 리스트입니다. 참고하기 위해서

이처럼 선입한 ArrayDeque의 값을 가져오고 가져온다면 그 값은 비어지고 다음 값을 가져올 수 있는 방식입니다.

따라서 ArrayDeque를 선언해주고, 그 값이 비어질 때까지 반복문을 생성하여 상,하,좌,우 로 이동하면서 cnt값을 구하고 map에 flag와 cnt를 넣어줍니다

마지막 값을 구할 때는

Set<Integer> set = new HashSet<>() 를 사용합니다.

Set은 중복된 값을 제외시키고 순서가 없는 것이 특징입니다.
flag 값은 한정되어 있으니 값을 다 넣어주고,
map에 저장되어있는 flag, cnt 를 출력하여 그 중 높은 값을 출력시키는 방식으로 해결한 것 같습니다.