프로그래머스 - PCCP 기출 2번 - BFS - Java

1. 문제

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

2. 풀이

✨핵심 Point

BFS로 땅을 count한다.

1. landNum을 통해 BFS로 탐색한 땅들의 번호를 부여한다.

2. HashMap에 landNum의 크기(count)를 넣어준다.

3. 열 별로 석유를 시추하면서 HashSet으로 landNum을 중복되지 않게 넣어주고, 해당 landNum에 해당하는 크기(count)를 더해 최댓값을 찾는다.

3. 전체 코드

import java.util.*;

class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        int n = land.length;
        int m = land[0].length;

        boolean visit[][] = new boolean[n][m];
        int[] moveX = {1, -1, 0, 0};
        int[] moveY = {0, 0, 1, -1};

        Queue<Integer> qX = new LinkedList<>();
        Queue<Integer> qY = new LinkedList<>();

        Map<Integer, Integer> map = new HashMap<>();
        int landNum = 1;

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if( land[i][j] == 0 || visit[i][j] )
                    continue;
                
                ArrayList<Integer> listX = new ArrayList<>();
                ArrayList<Integer> listY = new ArrayList<>();

                qX.add(i);
                qY.add(j);
                visit[i][j] = true;
                //listX.add(i);
                //listY.add(j);
                land[i][j] = landNum;
                int count = 1;

                while(!qX.isEmpty()){
                    int X = qX.poll();
                    int Y = qY.poll();

                    for(int mx = 0; mx < moveX.length; mx++){
                        int goX = X + moveX[mx];
                        int goY = Y + moveY[mx];

                        if(goX < 0 || goY < 0 || goX >= n || goY >= m)
                            continue;

                        if(land[goX][goY] == 0 || visit[goX][goY])
                            continue;

                        qX.add(goX);
                        qY.add(goY);
                        visit[goX][goY] = true;
                        //listX.add(goX);
                        //listY.add(goY);
                        land[goX][goY] = landNum;
                        count++;
                    }
                }

                map.put(landNum, count);
                // for(int l = 0; l < listX.size(); l++){
                //     //land[listX.get(l)][listY.get(l)] = count;
                //     land[listX.get(l)][listY.get(l)] = landNum;
                // }
                landNum++;
            }
        }

        for(int j = 0; j < m; j++){
            Set<Integer> oilSet = new HashSet<>();
            int oilSum = 0;
            for(int i = 0; i < n; i++){
                int oil = land[i][j];
                if(oil != 0 && !oilSet.contains(oil)) {
                    oilSet.add(oil);
                    //oilSum += oil;
                    oilSum += map.get(oil);
                }
            }
            answer = Math.max(answer, oilSum);
        }
        return answer;
    }
}