[알고리즘] PCCP 기출 문제 2번 Java

package org.example.알고리즘.PCCP기출문제2번;

import java.util.*;


class Solution {
    private static final int[] DX = {0, 0, -1, 1};
    private static final int[] DY = {1, -1, 0, 0};
    
    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}}));
        System.out.println("================================");
        System.out.println(solution.solution(new int[][]{{1, 0, 1, 0, 1, 1}, {1, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 0, 1}, {1, 0, 0, 1, 0, 0}, {1, 0, 0, 1, 0, 1}, {1, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1}}));
    }
    
    public int solution(int[][] land) {
        // x
        int xLength = land.length;
        // y
        int yLength = land[0].length;
        
        //각 칸의 석유 덩어리를 ID 로 저장한다.
        int[][] group = new int[xLength][yLength];
        //석유 덩어리 ID 와 그 크기를 저장한다.
        Map<Integer, Integer> groupSize = new HashMap<>();
        //석유 덩어리 ID
        int groupId = 1;
        
        //전체 맵을 스캔하며 석유 덩어리를 탐색하고 그 크기를 저장한다.
        for (int i = 0; i < xLength; i++) {
            for (int j = 0; j < yLength; j++) {
                if (land[i][j] == 1 && group[i][j] == 0) {
                    int size = bfs(land, group, i, j, groupId);
                    groupSize.put(groupId, size);
                    groupId++;
                }
            }
        }
        
        //각 열에 대해 석유 덩어리 크기 계산하여 가장 큰 친구를 저장해야한다
        int maxOil = 0;
        for (int y = 0; y < yLength; y++) {
            Set<Integer> columnGroupCount = new HashSet<>();
            int columnOil = 0;
            for (int x = 0; x < xLength; x++) {
                int currentGroupId = group[x][y];
                if (currentGroupId != 0 && !columnGroupCount.contains(currentGroupId)) {
                    columnOil += groupSize.get(currentGroupId);
                    columnGroupCount.add(currentGroupId);
                }
            }
            maxOil = Math.max(maxOil, columnOil);
        }
        
        return maxOil;
    }
    
    private int bfs(int[][] land, int[][] group, int x, int y, int groupId) {
        int xLength = land.length;
        int yLength = land[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        group[x][y] = groupId;
        int size = 1;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = current[0] + DX[i];
                int nextY = current[1] + DY[i];
                if (nextX >= 0 && nextY >= 0 && nextX < xLength && nextY < yLength && land[nextX][nextY] == 1 && group[nextX][nextY] == 0) {
                    queue.offer(new int[]{nextX, nextY});
                    group[nextX][nextY] = groupId;
                    size++;
                }
            }
        }
        
        return size;
    }
}

초안

1. 매번 열마다 bfs 를 도는 것으로 생각하고 문제를 진행했다.
   1. 실제로 시험에 나왔다면 백퍼 효율성에서 실패했을 것이다.

개선점

1. bfs 를 한번 순회를 하여
   1. 석유 덩어리 ID 를 각 land 에 매핑해주고
   2. 석유 덩어리 ID 에 대한 size 에 대한 HashMap 을 가지고 있으면 매번 bfs 를 돌 필요가 없어진다.

//전체 맵을 스캔하며 석유 덩어리를 탐색하고 그 크기를 저장한다.
        for (int i = 0; i < xLength; i++) {
            for (int j = 0; j < yLength; j++) {
                if (land[i][j] == 1 && group[i][j] == 0) {
                    int size = bfs(land, group, i, j, groupId);
                    groupSize.put(groupId, size);
                    groupId++;
                }
            }
        }

• group
  • 해당 칸의 석유 덩어리의 ID 로 저장한다
  • bfs 를 한번 순회할때 해당 부분에 그룹 ID 를 동일하게 설정해준다.

• bfs 돌고나서
  • groupSize 에 해당 groupId 에 대한 size 를 저장하고
  • groupId 를 한 개 증가시킨다.

2. 전부 돌아서 groupId 를 설정해주고 나면
   1. 다시 각 열에 대해 석유 덩어리 ID 가 중복되지 않도록 어떤게 들어가는지 체크해야한다.

   //각 열에 대해 석유 덩어리 크기 계산하여 가장 큰 친구를 저장해야한다
           int maxOil = 0;
           for (int y = 0; y < yLength; y++) {
               Set<Integer> columnGroupCount = new HashSet<>();
               int columnOil = 0;
               for (int x = 0; x < xLength; x++) {
                   int currentGroupId = group[x][y];
                   if (currentGroupId != 0 && !columnGroupCount.contains(currentGroupId)) {
                       columnOil += groupSize.get(currentGroupId);
                       columnGroupCount.add(currentGroupId);
                   }
               }
               maxOil = Math.max(maxOil, columnOil);
           }
           
           return maxOil;

   • 내부 for 문안에서 열을 하나씩 순회하면서 해당 열의 group 에는

     어떤 번호의 groupId 가 담겼는지 확인한다.

     해당 groupId 가 설정되었는지

     currentGroupId != 0 

     컬럼에 중복된 값이 들어가있는지

     !columnGroupCount.contains(currentGroupId)

     • Set 자료구조라 중복값은 들어가지 않을 텐데 왜? 라고 한다면
       • columnOil 값의 계산 때문이다.
       • 해당 열에 최대 몇사이즈의 덩어리가 들어가는지 체크할 수 있어야하기 때문이다.

하지만, 이 코드도 완벽하지는 않다. 효율성 테스트를 여러번 시도해야 통과한다.

일단 푸는데 2시간은 넘게 걸렸다

Uploaded by N2T