골드에그

1. 문제요약

코딩테스트 연습 - 미로 탈출 명령어 | 프로그래머스 스쿨 (programmers.co.kr)

(x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

l: 왼쪽으로 한 칸 이동
r: 오른쪽으로 한 칸 이동
u: 위쪽으로 한 칸 이동
d: 아래쪽으로 한 칸 이동

출발 위치, 도착 위치, 총 거리 K 가 주어질 때, 미로를 탈출하기 위한 경로를 구하시오.

2. 문제예제

문제 지문에 잘 나와있으므로 생략한다.

3. 팩트추출

Fact 1 : 사전 순으로 출력되려면 항상 d => l => r => u 순으로 탐색해야 한다. 지금 탐색 순서가 실패하면 아래 단계 순번으로 탐색하다가 다시 윗 단계 순번으로 탐색해야 한다.

Fact 2 : 2차원 배열로 구성되어 있는 그래프를 탐색하는데 위와 같이 특정한 조건이 존재하면 DFS 로 탐색하는 것이 좋다.

특정한 조건이란, 모두 비교하지 않고 도착이 가능한 형태인지 체크하는 문제이거나, 체인 형태로 탐색하는 순서(조건 존재)가 있는 경우이다. 해당 문제와 같이 실패했을 때도 탐색하는 순서가 정해져있다면 금상첨화다.

Fact 3 : 가지치기를 할 수 있다. 현재 위치에서 도착 위치까지 남은 거리와 남은 k 가 같은 짝수이거나 홀수이어야 한다. 짝 /홀이 다르다면, 어차피 도착을 못 하기 때문에 더 이상 탐색할 필요가 없다.

4. 문제전략

d => l => r => u 순서로 dfs 탐색하고 현재 위치에서 도착 위치까지 남은 거리와 남은 k 거리를 비교한다.

5. 소스코드

import java.util.*;

class Solution {
        // d, l, r, u 순으로 탐색
    private static final int[] dx = { 1, 0, 0, -1};
    private static final int[] dy = { 0, -1, 1, 0};
    private static final String[] term = {"d", "l", "r", "u"};
    private static int mapX, mapY;
    private static int endX, endY;
    private String tempAnswer = "";

    public boolean dfs(int x, int y, int k, String str, int diff) {
        if(k==0 && diff==0){
            tempAnswer = str;
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(nextX >=0 && nextY >= 0 && nextX < mapX && nextY < mapY && diff<=k) {
                if ((diff % 2 == 0 && k % 2 ==0) || (diff % 2 == 1 && k % 2 ==1)) {
                    if (dfs(nextX, nextY, k - 1, str + term[i], Math.abs(nextX - endX) + Math.abs(nextY - endY))) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer;
        mapX = n;
        mapY = m;
        endX = r-1;
        endY = c-1;
        int diff = Math.abs((r-1)-(x-1)) + Math.abs((c-1)-(y-1));
        dfs(x-1, y-1, k, "", diff);
        if(tempAnswer.equals("")){
            answer = "impossible";
        } else {
            answer = tempAnswer;
        }
        return answer;
    }
}

1. 문제

코딩테스트 연습 - 표 병합 | 프로그래머스 스쿨 (programmers.co.kr)

2. 팩트추출

Fact 1 : merge 커맨드와 unmerge 커맨드 보자마자 union-find 자료구조를 사용하면 된다는 것을 직감적으로 알 수 있다.

update 커맨드로 부모를 찾아 (집합 우두머리) 변경하고 merge, unmerge 커맨드로 부모 변수를 조정하면 끝이다.

3. 문제전략

union-find 자료구조!

4. 소스코드

class Solution {
    public int[] parent = new int[2501];
    public String[] value = new String[2501];

    //UNION-FIND 알고리즘
    public int find(int a) {
        if (parent[a] == a)
            return a;
        else
            return parent[a] = find(parent[a]);
    }

    public void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b)
            parent[b] = a;
    }

    //좌표를 번호로 변환
    public int convertNum(int x, int y) {
        int result = 50 * (x - 1);
        return result + y;
    }

    public String[] solution(String[] commands) {
        //초기화
        for (int i = 1; i <= 2500; i++) {
            parent[i] = i;
            value[i] = "";
        }

        //명령어 실행
        List<String> result = new ArrayList<>();
        for (int ind = 0; ind < commands.length; ind++) {
            String line = commands[ind];
            StringTokenizer st = new StringTokenizer(line);
            String command = st.nextToken();

            if ("UPDATE".equals(command)) {
                //UPDATE value1 value2
                if (st.countTokens() == 2) {
                    String before = st.nextToken();
                    String after = st.nextToken();
                    for (int i = 1; i <= 2500; i++) {
                        if (before.equals(value[i]))
                            value[i] = after;
                    }
                }
                //UPDATE x y value
                else {
                    int x = Integer.parseInt(st.nextToken());
                    int y = Integer.parseInt(st.nextToken());
                    String after = st.nextToken();
                    int num = convertNum(x, y);
                    value[find(num)] = after;
                }
            } else if ("MERGE".equals(command)) {
                int x1 = Integer.parseInt(st.nextToken());
                int y1 = Integer.parseInt(st.nextToken());
                int x2 = Integer.parseInt(st.nextToken());
                int y2 = Integer.parseInt(st.nextToken());
                int n1 = convertNum(x1, y1);
                int n2 = convertNum(x2, y2);
                int root1 = find(n1);
                int root2 = find(n2);
                //0. 같은 그룹이면 무시
                if (root1 == root2) continue;
                //1. 값을 가진쪽으로 병합
                String rootString = value[root1].isBlank() ? value[root2] : value[root1];
                value[root1] = "";
                value[root2] = "";
                union(root1, root2);
                value[root1] = rootString;
            } else if ("UNMERGE".equals(command)) {
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int num = convertNum(x, y);
                int root = find(num);
                String rootString = value[root];
                value[root] = "";
                value[num] = rootString;
                List<Integer> deleteList = new ArrayList<>();
                for (int i = 1; i <= 2500; i++) {
                    if (find(i) == root)
                        deleteList.add(i);
                }
                for (Integer t : deleteList)
                    parent[t] = t;
            } else if ("PRINT".equals(command)) {
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int num = convertNum(x, y);
                int root = find(num);
                if (value[root].isBlank())
                    result.add("EMPTY");
                else
                    result.add(value[root]);
            }
        }
        return result.toArray(new String[0]);
    }
}

1. 문제요약

코딩테스트 연습 - 표현 가능한 이진트리 | 프로그래머스 스쿨 (programmers.co.kr)

아래 과정을 수행해서 만들어지는 숫자를 포화 이진 트리로 표현 가능한 숫자라고 가정한다.

1. 이진수를 저장할 빈 문자열을 생성합니다.
2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
5. 문자열에 저장된 이진수를 십진수로 변환합니다.

반대로 숫자가 주어질 때, 포화 이진 트리로 표현 가능한지 구하시오.

2. 문제예제

문제 지문에 잘 나와있으므로 생략한다.

3. 팩트추출

Fact 1 : 문제에서 이야기하는 표현 가능한 이진트리는 트리 중앙에 있는 부모 노드의 값이 항상 있어야 한다는 특징을 가지고 있다. 그래서 중앙에 값이 있는지 체크하기 위해 포화 이진 트리 크기로 배열을 늘리고 중앙에 값이 있는지 재귀로 호출하면서 체크해야 한다. 전체 과정을 수행하기 위한 처리 루틴은 다음과 같다.

1. 숫자를 이진수로 바꾸었을 때, 이진수 자릿수를 구한다.
2. 이진수 자릿수를 포화 이진 트리 노드의 갯수만큼 늘린다.
3. 늘린 자릿수만큼 배열을 할당하고, 남은 앞 부분은 0 더미로 채운다.
4. 재귀로 호출하면서 트리의 서브트리 중앙 노드 값들을 값이 있는지 체크한다.

Fact 2 : 이진수로 표현했을 때 자릿수를 구하려면 중학교 때 배운 기수법과 로그의 성질을 이해해야 한다.

최종 m 번째 숫자가 결국 n 진법으로 나타냈을 때 자릿수와 같다. m * (n 진법 ^ m-1)

이 m 을 구하기 위해 log 를 활용하면 logn(10진수 숫자) + 1 이 된다. 

Fact 3 : 이진수 자릿수를 포화 이진 트리 노드의 갯수만큼 늘리려면 포화 이진 트리 노드의 갯수 공식을 알아야 한다.

트리 높이에 따라 포화 이진 트리 노드의 갯수를 구해보면 1, 3, 7, 15 ... 와 같은 수열임을 확인할 수있고, 이는  2^n-1 인 수식으로 표현이 가능하다. 즉, 이진수 자릿수보다 같거나 한 단계 큰 포화 이진 트리 노드의 갯수를 구하면 된다.

4. 문제전략

Fact 2 + Fact 3 공식과 DFS 로 트리를 절반씩 순회하면서 중앙에 있는 값이 0 인지 체크하면 된다. 

5. 소스코드

class Solution {
    public int treeLength;
    public int result;
    
    public void validateBinaryTree(boolean[] target, int start, int end, boolean isEnd) {
        int mid = (start + end) / 2;
        boolean current = target[mid];
        if (isEnd && current) {
            result = 0;
            return;
        }
        if (start != end) {
            validateBinaryTree(target, start, mid-1, !current);
            validateBinaryTree(target, mid+1, end, !current);
        }
    }

    private boolean[] makeTarget(long number) {
        int binaryLength = (int) Math.floor(Math.log(number) / Math.log(2)) + 1;

        int treeHeight = 1;
        treeLength = 0;
        while (treeLength < binaryLength) {
            treeLength = (int) Math.pow(2, treeHeight++) - 1;
        }

        boolean[] target = new boolean[treeLength];
        int i = treeLength - 1;
        while(true) {
            long div = number / 2;
            long mod = number % 2;
            number = div;
            target[i--] = (mod == 1);
            if (div == 1) {
                target[i] = true;
                break;
            } else if (div == 0) {
                break;
            }
        }
        return target;
    }
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        for (int i = 0; i < numbers.length ; i++) {
            result = 1;
            boolean[] target = makeTarget(numbers[i]);
            validateBinaryTree(target, 0, treeLength-1, false);
            answer[i] = result;
        }
        return answer;
    }
}

1. 문제요약

코딩테스트 연습 - 풍선 터트리기 | 프로그래머스 스쿨 (programmers.co.kr)

일렬로 나열된 n 개의 풍선이 있다. 풍선들을 아래 규칙에 따라 단 1개만 남을 때까지 하나씩 터트린다고 할 때 최후까지 남기는 것이 가능한 풍선들의 갯수를 구하시오.

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트린다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킨다.
3. 번호가 더 작은 풍선을 터트리는 행위는 한 번만 수행할 수 있다.

2. 문제예제

[9,-1,-5] 풍선이 주어질 때 다음과 같다.

• 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
• 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

3. 팩트추출

Fact 1 : 숫자가 낮은 풍선을 터트리는 행위는 한 번만 할 수 있으므로 모든 조합을 탐색할 필요는 없다. 탐색 방향에 맞춰 조합을 쪼개 규칙성을 찾는다. 일부 조합의 결과를 찾는 알고리즘과 전체 조합의 결과를 찾는 알고리즘이 같다면 DP 이다.

일단, 풍선의 갯수를 n 이라고 가정하고 n 이 점차 증가했을 때 규칙성을 찾아본다.

1) n 이 1 일 때,

무조건 풍선이 남아 있으므로 1 반환

2) n 이 2 일 때,

1번 풍선이 작고 2 번 풍선이 큰 경우와 1번 풍선이 크고 2번 풍선이 작은 경우로 나눌 수 있다.

낮은 풍선을 터트리는 찬스 없이도 큰 걸 제거할 수 있으므로 2 반환

3) n 이 3 일 때, 가운데 풍선을 기준으로 4 가지 경우의 수로 나눌 수 있다.

3-1) 왼쪽이 작고 오른쪽이 큰 경우

1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존

2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존

2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존

3-2) 왼쪽이 크고 오른쪽이 작은 경우

1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존

2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존

2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존

= 3-1 경우의 수와 같다.

3-3) 왼쪽도 작고 오른쪽도 작은 경우

1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존

3번을 제거하고 2번을 제거하면 (큰 것 => 큰 것 순) 1 생존

3번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 2 생존

2번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 1 생존

= 모든 경우의 수를 살펴봐도 중간값은 생존이 되지 않는다.

3-4) 왼쪽도 크고 오른쪽도 큰 경우

2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존

2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존

3번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 2 생존

현재 값보다 양 옆에 있는 숫자가 모두 작은 경우에만 생존하지 못 한다.

Fact 2 : 이전 결과 값이 그 다음에 영향을 미치지 않고 작은 문제들의 정답이 전체 문제의 정답이 되는 규칙성은 발견되지 않았다. (거의 모든 경우의 숫자가 살아 남으므로) 따라서 DP 나 분할 정복 문제는 아니다. 그러나 생존하지 못 하는 경우의 수로 보면 두 구역 모두 현재 숫자보다 작을 때 한 가지 경우의 수 밖에 없다. 따라서 경우의 수가 적은 여집합을 구한다.

Fact 3 : n 이 4일 때, 5일 때도 같은 규칙성이 존재하는지 확인한다. 작은 풍선을 제거하는 규칙을 사용하지 않고 큰 값만 골라 왼쪽, 오른쪽에서 제거한다면 항상 작은 값들만 배치하게 된다. 그렇게 n 이 3일 때로 만들고 위 규칙을 적용하면 결과값이 동일하다. 구역을 확장해도 해당 규칙에는 문제가 없다.

4. 문제전략

부분 문제로 보이지 않고 규칙성이 보이지 않으므로 완전 조합 문제로 풀어야 한다. 하지만 생존을 못 하는 여집합 경우의 수는 한 가지이므로 이 점을 고려하여 두 구역의 최솟 값보다 큰 경우의 숫자만 찾아 제외시켜 문제를 풀면 된다.

5. 소스코드

class Solution {
    public int solution(int[] a) {
        int count = 0;
        if (a.length == 1) return 1;
        if (a.length == 2) return 2;

        int leftMin = a[0];
        int rightMin[] = new int[a.length];
        rightMin[a.length-1] = a[a.length-1];

        for (int i = a.length - 2; i > 0; i--)
            rightMin[i] = Math.min(rightMin[i + 1], a[i]);

        for (int i = 0; i < a.length; i++) {
            if (!(leftMin < a[i] && rightMin[i] < a[i]))
                count++;
            leftMin = Math.min(leftMin, a[i]);
        }
        return count;
    }
}

1. 문제요약

코딩테스트 연습 - 다단계 칫솔 판매 | 프로그래머스 스쿨 (programmers.co.kr)

이 회사는 다단계 판매 업무를 하고 있다. 초대 받은 사람의 이익 10 퍼센트를 초대한 사람이 가지는 시스템인데 중앙에 있는 Center 까지 거슬러 올라가 모두 이익금을 나누어 가져야 한다.

판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어질 때, 각 판매원이 득한 이익금을 나열한 배열을 구하시오.

2. 문제예제

emily 가 450 원을 벌었다면, mary 는 10 퍼센트인 45 원을 가지게 되고, center 는 45원의 10 퍼센트인 40원을 가지게 된다.

3. 팩트추출

Fact 1 : 어렴풋이 보면 트리 자료구조 문제로 보일 수 있으나 enroll 입장에서 보면 부모가 하나이기 때문에 항상 일차원적인 구조이다. 따라서 부모노드까지 계속 재귀호출하면서 이익금을 계산해주면 된다. enroll 의 갯수만큼 반복문을 수행하고 이익금을 나누어 가지면 된다.

4. 문제전략

트리 문제라고 속지만 않으면 된다. enroll 을 순회하면서 이익금을 계산하면 된다.

5. 소스코드

import java.util.*;

class Solution {
   static class Person {
        String name;
        Person parent;
        int sellAmount;

        public Person(String name, Person parent, int sellAmount) {
            this.name = name;
            this.parent = parent;
            this.sellAmount = sellAmount;
        }

        public void calculateMultiLevel(int amount) {
            int parentAmount = amount / 10;
            this.sellAmount += amount - parentAmount;
            if (this.parent != null && parentAmount >= 1) {
                this.parent.calculateMultiLevel(parentAmount);
            }
        }
    }
    private static HashMap<String, Person> childParent;

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        childParent = new HashMap<>();
        for (String enrollP: enroll) {
            childParent.put(enrollP, new Person(enrollP, null, 0));
        }
        for (int i = 0; i < enroll.length; i++) {
            if (!referral[i].equals("-")) {
                childParent.get(enroll[i]).parent = childParent.get(referral[i]);
            }
        }
        for (int i = 0; i < seller.length ; i++) {
            childParent.get(seller[i]).calculateMultiLevel(amount[i] * 100);
        }
        int[] result = new int[enroll.length];

        for (int i = 0; i < result.length; i++) {
            result[i] = childParent.get(enroll[i]).sellAmount;
        }
        return result;
    }
}

1. 문제요약

코딩테스트 연습 - 양과 늑대 | 프로그래머스 스쿨 (programmers.co.kr)

이진 트리에 양과 늑대가 배치되어 있다. 각 노드에 방문할 때마다 양과 늑대를 모두 모아 데리고 다닐 수 있고,

모은 양의 수보다 늑대의 수가 같거나 더 많아지면, 양이 모두 잡아먹힌다. 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아 다시 루트 노드로 돌아오려 할 때, 최대로 모을 수 있는 양의 수를 구하라.

2. 문제예제

아래 접은 글을 확인해서 트리 노드를 어떻게 방문하는지 확인하면 된다.

3. 팩트추출

Fact 1 : 최대한 양을 많이 모아야 하므로 DFS 를 생각할 수 있다. 그런데 한 번 방문했던 자식 노드도 다시 탐색해야 하므로 일반적인 DFS 알고리즘과 다르다. 2번 문제 예제를 예로 들면, 0 => 1 노드로 탐색 실패했지만, 0 => 2 방문 후 1번 노드로 다시 방문할 수 있기 때문에 DFS 경로와는 다르다. 직접 탐색 리스트를 만들어 주어야 한다. 아래 Fact 2 번에서 자세히 다룬다.

Fact 2 : 현재 노드에서 갈 수 있는 경로를 정리해보자면, 아래 자식 노드들 뿐만 아니라 형제 노드의 자식 노드까지 가능하다. (거의 완전 탐색...) 일반적인 DFS 알고리즘은 다음 탐색할 노드가 자식 노드로 고정되어 있기 때문에 형제 노드를 가지고 오려면 부모 노드로부터 받아와야 한다. 탐색 실패해서 다시 부모노드로 돌아가더라도 갈 수 있는 모든 경로를 기억해야 한다. 부모 노드로부터 자식 노드의 경로들을 받아 그 리스트를 계속해서 전달해준다면 모든 탐색이 가능하다.

"경로" 를 인자로 주고 그 경로에서 뽑아 다음 방문할 지역을 선택하면 원래 DFS 경로 중간에 다른 경로를 추가로 검색할 수 있게 되는 트릭이 생긴다.

이 예제로 설명을 해보자면, 오른쪽 트리에서 DFS 를 수행하다가 자식 노드 끝까지 마저 탐색하지 않고 왼쪽 트리로 방문한다. 이렇게 해도 정보가 꼬이지 않는 이유는 부모 노드로부터 정보를 받은 것은 재활용할 수 있기 때문이다. DFS 이기 때문에 또 트리(순환하지 않는 그래프)이기 때문에 같은 정보를 공유하는 다른 형제노드부터 탐색이 가능한 것이다. 

Fact 3 : 부모 노드에서 자식 노드들을 탐색 리스트에 넣고 그 리스트가 삭제가 되지 않고 계속 추가되므로 자신의 노드가 리스트에 계속 살아있을 수 있다. 따라서 자기 자신은 경로 리스트에서 제외해야 한다.

4. 문제전략

팩트추출에서 소개한 DFS 변형 알고리즘을 사용해서 문제를 푼다.

5. 소스코드

import java.util.*;

class Solution {
    private static int answer;
    private static final List<List<Integer>> GRAPH = new LinkedList<>();

    public int solution(int[] info, int[][] edges) {
        answer = 0;
        for (int i = 0; i < info.length; i++) {
            GRAPH.add(new LinkedList<>());
        }

        for (int[] edge : edges) {
            GRAPH.get(edge[0]).add(edge[1]);
        }

        final List<Integer> next = new LinkedList<>();
        next.add(0);

        dfs(info, next, 0, 0, 0);

        return answer;
    }

    private void dfs(int[] info, List<Integer> list, int node, int sheep, int wolf) {
        if (info[node] == 0) {
            sheep += 1;
        } else {
            wolf += 1;
        }

        if (sheep <= wolf) {
            return;
        }

        answer = Math.max(answer, sheep);

        List<Integer> next = new ArrayList<>(list);
        if (!GRAPH.get(node).isEmpty()) {
            next.addAll(GRAPH.get(node));
        }
        next.remove(Integer.valueOf(node));

        for (int n : next) {
            dfs(info, next, n, sheep, wolf);
        }
    }
}

1. 문제요약

코딩테스트 연습 - 등산코스 정하기 | 프로그래머스 스쿨 (programmers.co.kr)

출입구에서 산봉우리까지 갔다가 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다.

등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity 라고 할 때 이 intensity 가 가장 짧은 코스를 찾아라. (등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다.)

2. 문제예제

등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같다.

각 경로의 가중치가 가장 큰 값이 3 이며, 이 보다 intensity가 낮은 등산코스는 없다.

3. 팩트추출

Fact 1 : Dijkstra 다이젝스트라 알고리즘처럼 항상 최단 거리를 선택한다면, 경로의 intensity 배열은 항상 단조 증가 형태이다. 이 점을 활용하면 출발점에서 산봉우리까지 갔다가 다시 출발점으로 돌아오지 않아도 된다. 출발점에서 산봉우리까지 가는 반쪽짜리 최단 경로만 찾으면 된다. 출발 경로와 회귀 경로가 틀릴 수 있을지 언정 intensity 는 같을 것이기 때문이다. 이 문제에서는 경로를 구하라고 하지 않았으므로 가능하다. => 따라서 큐에 꺼낸 위치가 산봉우리라면 탐색을 종료한다.

Fact 2 : Fact 1 과 마찬가지로 경로를 구하라고 하지는 않았으므로, 출발점에서 동시에 출발하여 intensity 배열을 수정하여도 상관이 없다. 문제에서 요구하는 정답은 산봉우리와 그 산봉우리의 intensity 이다. 그러니까 어느 출발점에서 출발하여도 도착지점의 intensity 가 최소가 되는 경로만 찾으면 된다. 따라서 우선순위 큐에 출발지점을 모두 넣어놓고 시작한다.

Fact 3 : 일반적인 Dijkstra 다이젝스트라 알고리즘과 다른 점은 각 지점의 비용을 합한 거리가 최소가 되는 경로를 찾는 것이 아니라 각 구간의 최대 비용이 최소가 되는 경로를 찾는 것이다. 따라서 아래와 같이 로직을 수정한다.

if(dist[adjNode.to] > curNode.weight + adjNode.weight){
	dist[adjNode.to] = curNode.weight + adjNode.weight;
}

↓↓↓↓↓↓

if (dist[adjNode.to] > Math.max(curNode.weight, adjNode.weight)) {
	dist[adjNode.to] = effort;
}

Fact 4 : 산봉우리까지 가는 intensity 가 같은 경로가 여러 개라면, 산봉우리의 번호가 가장 작은 것을 반환하라고 지문에서 나와있으므로 산봉우리-intensity 배열에서 최소값을 찾을 때 산봉우리 배열을 먼저 정렬해야 한다.

4. 문제전략

팩트추출에서 소개한 다이젝스트라 변형 알고리즘을 사용하면 된다.

5. 소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    static class Node implements Comparable<Node> {
        int index;
        int effort;
        public Node(int index, int effort) {
            this.index = index;
            this.effort = effort;
        }
        @Override
        public int compareTo(Node o) {
            return this.effort - o.effort;
        }
    }
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] efforts;
    static int[] gatesSave, summitsSave;
    private static void initGraph(int v, int[][] data) {
        for(int i=0; i < v+1; i++){
            graph.add(new ArrayList<>());
        }
        for (int[] datum : data) {
            graph.get(datum[0]).add(new Node(datum[1], datum[2]));
            graph.get(datum[1]).add(new Node(datum[0], datum[2]));
        }
        efforts = new int[v+1];
        for (int i = 1; i < v+1; i++) {
            efforts[i] = Integer.MAX_VALUE;
        }
    }

    private static int[] dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        // 시작지점 삽입
        for (int gate : gatesSave) {
            pq.offer(new Node(gate, 0));
            efforts[gate] = 0;
        }

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (isSummit(curNode.index))
                continue;
            if (efforts[curNode.index] < curNode.effort) {
                continue;
            }
            for (Node adjNode : graph.get(curNode.index)) {
                int effort = (adjNode.effort == Integer.MAX_VALUE) ? curNode.effort : Math.max(curNode.effort, adjNode.effort);
                if (efforts[adjNode.index] > effort) {
                    efforts[adjNode.index] = effort;
                    pq.offer(new Node(adjNode.index, efforts[adjNode.index]));
                }
            }
        }

        Arrays.sort(summitsSave);
        int index = -1;
        int minEffort = Integer.MAX_VALUE;
        for (int summit : summitsSave) {
            if (efforts[summit] < minEffort) {
                minEffort = efforts[summit];
                index = summit;
            }
        }
        return new int[]{index, minEffort};
    }

    private static boolean isSummit(int num) {
        for (int summit : summitsSave) {
            if (num == summit) return true;
        }
        return false;
    }

    public static int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        gatesSave = gates;
        summitsSave = summits;
        initGraph(n, paths);
        return dijkstra();
    }
}

1. 문제요약

코딩테스트 연습 - 기둥과 보 설치 | 프로그래머스 스쿨 (programmers.co.kr)

n x n 크기의 2차원 벽면에 기둥(세로) 와 보(가로) 를 설치해 구조물을 만들려고 한다.

벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame 이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성하라.

룰은 다음과 같다.

① 기둥과 보는 1 X 1 크기의 격자이다. 격자 칸의 각 변에 정확히 일치하도록 설치하여야 한다.

② 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다.

③ 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.

2. 문제예제

3. 팩트추출

Fact 1 : 한 지점에서 기둥과 보를 같이 설치/해제할 수 있으므로, map 2차원 배열에 기둥과 보에 대한 정보를 같이 삽입할 수 없다. 기둥의 설치 여부를 나타내는 map 하나와 보의 설치 여부를 나타내는 map 하나를 각각 준비해야 한다.

Fact 2 : 위 문제예제에서도 살펴보았듯이 명령어를 순서대로 적용할 때 실시간으로 가능 여부를 체크해야 한다.

4. 문제전략

문제전략이라고 할 것이 없다. 명령어를 하나씩 받고 아래 2번 3번 룰에 어긋나지 않는지만 체크하면 된다.

② 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다.

③ 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.

5. 소스코드

class Solution {
    static int N;
    static boolean[][] column;
    static boolean[][] row;

    public enum materialType {
        COLUMN(0), ROW(1);
        private final int indexNumber;
        materialType(int i) { this.indexNumber = i; }
        public int getIndex() { return indexNumber; }
    };

    public enum constructType {
        DESTRUCT(0), CONSTRUCT(1);
        private final int indexNumber;
        constructType(int i) { this.indexNumber = i; }
        public int getIndex() { return indexNumber; }
    };
    public int[][] solution(int n, int[][] build_frame) {
        int structureCount = 0;
        N = n;
        column = new boolean[n + 2][n + 2];
        row = new boolean[n + 2][n + 2];

        for(int[] frame : build_frame){
            int x = frame[0] + 1;
            int y = frame[1] + 1;
            int structureType = frame[2];
            int commandType = frame[3];

            if(commandType == constructType.CONSTRUCT.getIndex()){
                if(structureType == materialType.COLUMN.getIndex() && checkColumn(x, y)){
                    column[x][y] = true;
                    structureCount++;
                }
                if(structureType == materialType.ROW.getIndex() && checkRow(x, y)){
                    row[x][y] = true;
                    structureCount++;
                }
            } else if(commandType == constructType.DESTRUCT.getIndex()){
                if(structureType == materialType.COLUMN.getIndex()){
                    column[x][y] = false;
                } else if(structureType == materialType.ROW.getIndex()) {
                    row[x][y] = false;
                }
                if(canDestruct(x, y)) {
                    structureCount--;
                    continue;
                }
                if(structureType == materialType.COLUMN.getIndex()){
                    column[x][y] = true;
                } else if(structureType == materialType.ROW.getIndex()) {
                    row[x][y] = true;
                }
            }
        }

        int index = 0;
        int[][] answer = new int[structureCount][3];

        for(int i = 1 ; i <= n + 1 ; ++i){
            for(int j = 1 ; j <= n + 1 ; ++j){
                if(column[i][j]) answer[index++] = new int[]{i - 1, j - 1, materialType.COLUMN.getIndex()};
                if(row[i][j]) answer[index++] = new int[]{i - 1, j - 1, materialType.ROW.getIndex()};
            }
        }
        return answer;
    }
    private boolean checkColumn(int x, int y) {
        return y == 1 || column[x][y - 1] || row[x - 1][y] || row[x][y];
    }

    private boolean checkRow(int x, int y) {
        return column[x][y - 1] || column[x + 1][y - 1] || (row[x - 1][y] && row[x + 1][y]);
    }

    private boolean canDestruct(int x, int y) {
        for(int i = 1 ; i <= N + 1 ; ++i){
            for(int j = 1 ; j <= N + 1 ; ++j){
                if(column[i][j] && !checkColumn(i, j)){
                    return false;
                }
                if(row[i][j] && !checkRow(i, j)){
                    return false;
                }
            }
        }
        return true;
    }
}