CODEKATA 117 ~ 118

117번 마법의 엘리베이터

/*
문제 분석
1. 정보
    - 아주 높은 탑이 존재. 탑이 너무 높아 마법의 엘리베이터를 만들음.
    - 해당 버튼은 특별함
        - -1, +1, -10, +10, -100, +100등과 같이 절댓값이 10^c 형태인 정수들이 적힌 버튼이 존재
        - 버튼을 누르면 현재 층 수에 버튼에 적혀있는 값을 더한 층으로 이동
        - 단 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않음
        - 엘리베이터는 현재 민수가 있는 층에 있음
    - 엘리베이터를 움직이기 위해서 버튼 한 번당 마법의 돌 한 개를 사용하게 됨

2. 목표
    - 0층으로 가기 위해 필요한 마법의 돌의 최솟값을 return

3. 제약 조건
    - 1 <= 현재 민수가 위치한 층 <= 100_000_000

풀이
1. 아이디어
    - storey 를 1의 자리 부터 계산
    - DFS 사용
        - 1의 자리가 5를 기준으로 작다면
            - storey - 해당 수 and storey /= 10
            - DFS(storey, 이동 횟수 + 해당 수) 해줌
        - 1의 자리가 5를 기준으로 크다면
            - storey + 해당 수 and storey /= 10
            - DFS(storey, 이동 횟수 + 해당 수) 해줌
        - storey가 0이라면, 해당 이동 횟수가 가장 적은 이동 횟수
     - 해당 문제점
        - 만약 95와 같은 숫자라면, 90 보다 100 이 이득임.
        - 따라서 5를 기준으로 따로 계산하는것이 아닌,
        - 해당 숫자를 기준으로 뺐을때와 더했을때 모두를 계산하여 최솟값을 구해야함.
        - 추가 문제점
            - 1의자리까지 갔을 시, 숫자를 더해 10의자리를 만들고 다시 1의자리로 만드는 작업이 무한루프 발생
            - 따라서 현재 위치가 1보다 클때만 10의 자리로 올리는것을 허용
                - 한번 10의 자리로 올리면 다음 수는 1로 나오기 때문
*/

class Solution {
        int answer = 100_000_001;
        public int solution(int storey) {
            compute(storey, 0);
            return answer;
        }

        private void compute(int storey, int cnt) {
            if (storey == 0) {
                answer = Math.min(answer, cnt);
                return;
            }

            int cur = storey % 10;
            compute(storey / 10, cnt + cur);
            if (storey > 1) {
                compute((storey + (10 - cur)) / 10, cnt + (10 - cur));
            }
        }
    }

118번 거리두기 확인하기

/*
문제 분석
1. 정보
    - 코로나 감염 예방을 위해 거리를 둬서 대기. 규칙은 다음과 같음
        - 대기실은 5개이며, 각 대기실은 5X5 크기
        - 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말 것
        - 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용

2. 목표
    - 대기실의 구조를 대기실 별로 담은 places가 주어질 때, 각 대기실 별로 거리두기를 지키고 있으면 1, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return
3. 제약 조건
    - 대기실의 개수, 행 길이, 열 길이 = 5
    - 원소는 P O X로 이루어짐
        - P : 앉아있는 자리
        - O : 빈 테이블
        - X : 파티션

풀이
1. 아이디어
    - 각 대기실 별로 계산
        - 현재 대기실에서 모든 응시자들에 대하여 계산
            - 해당 응시자를 기준으로 파티션을 제외한 2칸 이하에 응시자가 있을 경우 바로 0
            - 없다면 다음 응시자 선택
        - 모든 응시자가 거리두기를 지키고 있다면, 1 반환

    - 해당 대기실 0,0 부터 4,4까지 순회
        - 해당 좌표에 응시자 있다면
            - BFS 활용 (x,y,거리)담은 Node class 생성
            - Queue를 이용해 거리가 2이하인 곳만 탐색
            - 파티션은 지날 수 없음
            - 거리가 2 이하인 곳에 응시자 존재한다면 0 반환
            - 큐가 끝날때까지 응시자 존재하지 않는다면 다음 응시자 찾음
    - 해당 대기실 모두 순회하고도 거리두기 잘 지켜졌다면 1 반환
*/

import java.util.*;

class Solution {

        class Node {
            int x;
            int y;
            int d;

            public Node(int x, int y, int d) {
                this.x = x;
                this.y = y;
                this.d = d;
            }
        }

        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        public int[] solution(String[][] places) {
            int[] answer = new int[5];

            for (int i = 0; i < 5; i++) {
                answer[i] = compute(places[i]);
            }
            return answer;
        }

        private int compute(String[] place) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (place[i].charAt(j) == 'P') {
                        Queue<Node> q = new LinkedList<>();
                        boolean[][] visited = new boolean[5][5];
                        q.add(new Node(i, j, 0));
                        visited[i][j] = true;
                        while (!q.isEmpty()) {
                            Node cur = q.poll();
                            if (cur.d == 2) {
                                continue;
                            }
                            for (int k = 0; k < 4; k++) {
                                int nx = cur.x + dx[k];
                                int ny = cur.y + dy[k];

                                if (isAvailable(nx, ny) && !visited[nx][ny]) {
                                    char next = place[nx].charAt(ny);
                                    if (next == 'P') {
                                        return 0;
                                    } else if (next == 'O') {
                                        visited[nx][ny] = true;
                                        q.add(new Node(nx, ny, cur.d + 1));
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return 1;
        }

        private boolean isAvailable(int nx, int ny) {
            return nx >= 0 && nx < 5 && ny >= 0 && ny < 5;
        }
    }