프로그래머스 시험장 나누기, 백준 21610

🤣 프로그래머스 : 시험장 나누기 

사실 이것은 ... 직접 푼 문제는 아니긴 하다.

하지만 그냥 공부한 셈 치고 정리 겸 올려 본다... 카카오 코테 문제이고, 오랜만에 프로그래머스 들어갔다가 추천 문제라며 띄워주길래 그냥 하나 풀어봐야겠다~ 하고 푸는데 답이 도저히 안 나와서 해설을 찾았다...

걍 고수의 풀이를 보고 이해한거 정리한 거라고 생각하면 된다. 

보니깐 마지막 문제로 나온거던데 여기까지 가지도 못하고 끝나지 않았을까 싶다. 

 

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

프로그래머스

 

이분의 해설과 코드를 보고 풀었다. 잘 정리가 되어 있으니 참고하길.. 

https://blog.encrypted.gg/1003

[2021 카카오 채용연계형 인턴십] Q5. 시험장 나누기 (C++, Python, Java)

 

 

문제 유형이 Parametric Search 인데 이 유형은 이전에 풀었던 2110 공유기 문제와 동일한 유형이다. https://bubblebubble.tistory.com/109 

이 문제는 각 그룹의 수를 x명으로 하는 경우에 그룹의 수가 K개 이하라는 문제조건을 만족하는가? 만족하면 x 기준을 더 낮게 잡고 아니면 더 높이는 방식으로 최적의 X명을 찾아간다.

이 그룹당 최대 인원수를 이진탐색을 통해 제한했다면, 각 그룹의 개수는 DFS 통해서 카운트 할 수 있다. 연결된 애들을 다 탐색하고 돌기 오기 때문이다! 

 

 

전체코드 : 매우... 간결하다. 

import java.util.*;
class Solution {
    int[] left = new int[10001];
    int[] right = new int[10001];
    int[] parent = new int[10001];
    int[] value = new int[10001];
    int n, root;
    int count = 0;
    
    public int solution(int k, int[] num, int[][] links) {
        n = num.length;
        for (int i = 0; i < n; i++) {
            parent[i] = -1;
        }
        for (int i = 0; i < n; i++) {
            left[i] = links[i][0];
            right[i] = links[i][1];
            value[i] = num[i];
            
            if (left[i] != -1) 
                parent[left[i]] = i;
            if (right[i] != -1)
                parent[right[i]] = i;
        }
        
        for (int i = 0; i < n; i++) {
            if (parent[i] == -1) {
                root = i;
                break;
            }
        }
        
        int start = value[0];
        int end = (int)1e8;
        for (int i = 0; i < n; i++) {
            if (start < value[i]) {
                start = value[i];
            }
            
        }
        
        while (start < end) {
            int mid = (start + end) / 2;
            int temp = calculate(mid);
            if (temp <= k) {
                end = mid;
            } else {
                start = mid+1;
            }
        }
        
        return start;
    }
    
    public int calculate(int limit) {
        count = 0;
        DFS(root, limit);
        
        count++;
        return count;
    }
    
    public int DFS(int index, int limit) {
        int leftChild = 0;
        if (left[index] != -1) {
            leftChild = DFS(left[index], limit);
        }
        
        int rightChild = 0;
        if (right[index] != -1) {
            rightChild = DFS(right[index], limit);
        }
        
        if (rightChild + leftChild + value[index] <= limit) {
            return rightChild + leftChild + value[index];
        } else if (Math.min(rightChild, leftChild) + value[index] <= limit) {
            count++;
            return Math.min(rightChild, leftChild) + value[index];
        } else {
            count += 2;
            return value[index];
        }
    }
}

 

 

---

🦈 백준 21610 : 마법사 상어와 비바라기 

https://www.acmicpc.net/problem/21610

21610번: 마법사 상어와 비바라기

비바라기를 보면 포켓* 기술이 생각난다. 말 그대로 필드에 비 내리게 하는 기술

 

🦈 삼성 기출문제중에 골드 5로 난이도만 보면 나름 쉬워보이지만... 삼성 기출들이 다 그렇듯, 조건이 많다보니 빼먹으면 아주... 헤매게 되어 있는 문제이다. 그리고 난 항상 빼먹는다. 진짜 배열 다 그려가면서 어디가 틀린건지 찾았는데 매우 허무했다.

🦈 메인 로직은 아래 처럼 구성되어 있다.

🦈 구름 움직이기 - 비 내리기 - 물 복사 마법 - 구름 위치 초기화 - 다음 구름 위치 cloud 리스트에 넣어줌 - 방문배열 초기화(이전에 구름이 생겼던 곳은 다음 구름 초기 위치가 될 수 없다!)

moveCloud(dir, length);
makeRain();
waterCopy();
clouds = new ArrayList<>();
findCloudPos();
visited = new boolean[n][n];

🦈 구름 움직이기

• 기존 clouds 리스트에는 일단 초기에 지정한 구름 발생 위치가 담겨 있다. 
• 각 위치들 하나하나가 다 방향에 맞춰 일괄 이동해야 하는데 무슨 군집형태로 이동하는 것도 아니기 때문에 일일이 이동시켜준 뒤, 이동된 좌표를 다시 clouds에 넣어주었다. 

private static void moveCloud(int dir, int length) {
        List<Pos> newCloud = new ArrayList<>();
        for (Pos cloud : clouds) {
            int nextX = (cloud.x + dirX[dir-1] * length) % n;
            if (nextX < 0) {
                nextX += n;
            }
            int nextY = (cloud.y + dirY[dir-1] * length) % n;
            if (nextY < 0) {
                nextY += n;
            }
            if (visited[nextX][nextY]) {
                continue;
            }
            newCloud.add(new Pos(nextX, nextY));
            visited[nextX][nextY] = true;
        }
        clouds = new ArrayList<>(newCloud);
}

 

 

🦈 makeRain은 그냥 비 내리게 하는 함수이다. 각 map 칸에 +1 해주는 로직

private static void makeRain() {
        for (Pos cloud : clouds) {
            map[cloud.x][cloud.y]++;
        }
}

 

🦈 waterCopy 

• 대각선 4방향은 dir 값이 2, 4, 6, 8이다. 나는 그냥 방향을 0부터 시작해서 구현했으므로 각 비온 자리마다 1,3,5,7 방향으로 탐색해주면 된다. 
• 여기서는 넘어가는게 허용되지 않는다. (맨 끝에서 대각선되면 다른 대각선으로 넘어가고 이런거)
  • 이게 허용되지 않아서 골드 5인가 싶기도..? 
• 쨌든 그래서 범위를 벗어나거나, 바구니 칸 물이 0이라면 내버려두고, count 개수 센 다음 addRain 리스트에 더해준다.
  • 이것도 한번에 계속 차례대로 더하면 다음 좌표가 영향을 받을 수 있으므로, 따로 리스트에 빼서 넣어주고 마지막 for문에서 한번에 넣어주는 것

private static void waterCopy() {
        List<Integer> addRain = new ArrayList<>();
        for (Pos cloud : clouds) {
            int count = 0;
            for (int i = 1; i < 8; i += 2) {
                int nextX = cloud.x + dirX[i];
                int nextY = cloud.y + dirY[i];

                if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) {
                    continue;
                }
                if (map[nextX][nextY] == 0) {
                    continue;
                }
                count++;
            }
            addRain.add(count);
        }

        for (int i = 0; i < addRain.size(); i++) {
            map[clouds.get(i).x][clouds.get(i).y] += addRain.get(i);
        }
    }

 

🦈 findCloudPos 

• 이전에 구름 있던 장소(visited true)가 아니고, 물의 양이 2 이상인 경우에만 구름 초기 위치로 지정해준다. 

private static void findCloudPos() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j]) {
                    continue;
                }
                if (map[i][j] >= 2) {
                    map[i][j] -= 2;
                    clouds.add(new Pos(i, j));
                }
            }
        }
}

 

🦈 전체 코드 

import java.io.*;
import java.util.*;
public class p21610 {
    private static int[] dirX = { 0, -1, -1, -1, 0, 1, 1, 1 };
    private static int[] dirY = { -1, -1, 0, 1, 1, 1, 0, -1 };
    private static int n, m;
    private static List<Pos> clouds;
    private static int[][] map;
    private static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        clouds = new ArrayList<>();
        map = new int[n][n];
        visited = new boolean[n][n];

        int answer = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        clouds.add(new Pos(n-1, 0));
        clouds.add(new Pos(n-1, 1));
        clouds.add(new Pos(n-2, 0));
        clouds.add(new Pos(n-2, 1));

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int dir = Integer.parseInt(st.nextToken());
            int length = Integer.parseInt(st.nextToken());

            moveCloud(dir, length);
            makeRain();
            waterCopy();
            clouds = new ArrayList<>();
            findCloudPos();
            visited = new boolean[n][n];
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                answer += map[i][j];
            }
        }

        System.out.println(answer);
    }

    private static void findCloudPos() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j]) {
                    continue;
                }
                if (map[i][j] >= 2) {
                    map[i][j] -= 2;
                    clouds.add(new Pos(i, j));
                }
            }
        }
    }
    private static void moveCloud(int dir, int length) {
        List<Pos> newCloud = new ArrayList<>();
        for (Pos cloud : clouds) {
            int nextX = (cloud.x + dirX[dir-1] * length) % n;
            if (nextX < 0) {
                nextX += n;
            }
            int nextY = (cloud.y + dirY[dir-1] * length) % n;
            if (nextY < 0) {
                nextY += n;
            }
            if (visited[nextX][nextY]) {
                continue;
            }
            newCloud.add(new Pos(nextX, nextY));
            visited[nextX][nextY] = true;
        }
        clouds = new ArrayList<>(newCloud);
    }

    private static void makeRain() {
        for (Pos cloud : clouds) {
            map[cloud.x][cloud.y]++;
        }
    }

    private static void waterCopy() {
        List<Integer> addRain = new ArrayList<>();
        for (Pos cloud : clouds) {
            int count = 0;
            for (int i = 1; i < 8; i += 2) {
                int nextX = cloud.x + dirX[i];
                int nextY = cloud.y + dirY[i];

                if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) {
                    continue;
                }
                if (map[nextX][nextY] == 0) {
                    continue;
                }
                count++;
            }
            addRain.add(count);
        }

        for (int i = 0; i < addRain.size(); i++) {
            map[clouds.get(i).x][clouds.get(i).y] += addRain.get(i);
        }
    }

    private static class Pos {
        int x;
        int y;
        public Pos (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}