Job Boot Camp : Week 02 Report

codesver·2022년 10월 18일

job boot camp

Job Boot Camp

목록 보기

3/6

📌 Max Heap

Question. Max heap 알고리즘을 구현하여라

📍 Implement

Code

package report02;

import java.util.ArrayList;
import java.util.List;

public class MaxHeap {

    private final List<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList<>();
    }

    public MaxHeap(List<Integer> eleArr) {
        heap = new ArrayList<>();
        insertAll(eleArr);
    }

    // Inserting element
    public void insert(Integer ele) {
        heap.add(ele);                                          // Add element to tail of heap
        int idx = heap.size() - 1;                              // Index of tail element
        int pIdx = (idx - 1) / 2;                               // Index of parent element of tail element

        while (idx > 0 && heap.get(pIdx) < heap.get(idx)) {     // If index is not root and child value is bigger than parent
            swap(pIdx, idx);
            idx = pIdx;                                         // Change child index to parent index
            pIdx = (pIdx - 1) / 2;                              // Change parent index to parent of itself
        }
    }

    // Inserting elements
    public void insertAll(List<Integer> eleArr) {
        for (Integer ele : eleArr) insert(ele);
    }

    // Search max value element and delete from heap
    public Integer delete() {
        if (heap.size() == 0) return null;              // When no element exist
        if (heap.size() == 1) return heap.remove(0);    // When single element exist

        // When more than one element exist
        swap(0, heap.size() - 1);                       // Swap root and tail
        Integer value = heap.remove(heap.size() - 1);   // Remove tail
        heapify(0, heap.size() - 1);                    // Heapify from root
        return value;
    }

    // Swap elements
    private void swap(int idxA, int idxB) {
        Integer temp = heap.get(idxA);
        heap.set(idxA, heap.get(idxB));
        heap.set(idxB, temp);
    }

    // Heapify (from idx to maxIdx)
    private void heapify(int idx, int maxIdx) {
        int lcIdx = idx * 2 + 1;                                            // Left child index
        int rcIdx = lcIdx + 1;                                              // Right child index

        int mvcIdx = 0;                                                     // Max value child index
        if (maxIdx < lcIdx && maxIdx < rcIdx) return;                       // When both child is out of range
        else if (lcIdx == maxIdx) mvcIdx = lcIdx;                           // When left child is tail
        else mvcIdx = heap.get(lcIdx) > heap.get(rcIdx) ? lcIdx : rcIdx;    // Bigger value child's index

        if (heap.get(idx) >= heap.get(mvcIdx)) return;                      // Return when parent value is bigger
        swap(idx, mvcIdx);                                                  // Swap parent and child
        heapify(mvcIdx, maxIdx);                                            // Recursive heapify
    }

    // Sorting
    public void sort() {
        for (int i = 0; i < heap.size(); i++) {
            swap(0, heap.size() - 1 - i);       // Swap root and tail of range which is not sorted
            heapify(0, heap.size() - 2 - i);   // Heapify from root to tail of range which is not sorted
        }
    }

    @Override
    public String toString() {
        return heap.toString();
    }
}

📌 Dijkstra Algorithm

Question. 다익스트라 알고리즘을 구현하고 최적 경로를 출력하고 확인하여라. 음의 가중치가 있는 경우에도 적용되는지 확인하여라

📍 Implement

Graph

Code

import java.util.Arrays;

public class Graph {

    private final int size;
    private final int[][] weights;

    private final int INF = Integer.MAX_VALUE;

    // Constructor
    public Graph(int size) {
        this.size = size;
        weights = new int[size][size];

        // Init weights to INF
        for (int i = 0; i < size; i++)
            Arrays.fill(weights[i], INF);
    }

    // Input weight
    public void input(int from, int to, int weight) {
        weights[from][to] = weight;
        // weights[to][from] = weight; (Bi-directional graph)
    }

    public int size() {
        return size;
    }

    public int[][] getWeights() {
        return weights;
    }
}

Dijkstra

Code

import java.util.Arrays;

public class Dijkstra {

    private int[] distance;
    private boolean[] visited;

    private final Graph graph;

    private final int INF = Integer.MAX_VALUE;

    // Constructor
    public Dijkstra(Graph graph) {
        this.graph = graph;
    }

    // Dijkstra Algorithm
    public void algorithm(int start) {
        int size = graph.size();
        int[][] weights = graph.getWeights();
        init(start, size, weights);
        main(start, size, weights);
    }

    // Init
    private void init(int start, int size, int[][] weights) {
        distance = new int[size];
        visited = new boolean[size];
        Arrays.fill(distance, INF);
        distance[start] = 0;
        visited[start] = true;

        for (int i = 0; i < size; i++)
            if (!visited[i] && weights[start][i] != INF)
                distance[i] = weights[start][i];
    }

    // Main
    private void main(int start, int size, int[][] weights) {
        for (int i = 0; i < size - 1; i++) {
            int minV = INF;     // Min value to node
            int minI = -1;      // Min value index

            for (int j = 0; j < size; ++j) {
                if (!visited[j])                    // When not visited
                    if (distance[j] < minV) {       // And distance is smaller than min
                        minV = distance[j];         // New min value
                        minI = j;                   // New min index
                    }
            }
            if (minI != -1) {
                visited[minI] = true;
                for (int j = 0; j < size; ++j) {
                    if (!visited[j] && weights[minI][j] != INF)                 // Not visited and can go to j node
                        if (distance[minI] + weights[minI][j] < distance[j])    // When transferring minIdx is faster
                            distance[j] = distance[minI] + weights[minI][j];    // Change min distance
                }
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < graph.size(); i++) {
            builder.append("Distance to node ").append(i).append(" = ")
                    .append(distance[i]).append("\n");
        }
        return builder.toString();
    }
}

📍 Testing

Graph

양의 가중치 그래프
음의 가중치 그래프

Result

양의 가중치 그래프의 각 점에서 최단 거리

=====Starting from node 0=====
Distance to node 0 from node 0 = 0
Distance to node 1 from node 0 = 3
Distance to node 2 from node 0 = 4
Distance to node 3 from node 0 = 2
Distance to node 4 from node 0 = 6
Distance to node 5 from node 0 = 3
Distance to node 6 from node 0 = 4
Distance to node 7 from node 0 = 5
Distance to node 8 from node 0 = 8
Distance to node 9 from node 0 = 5
==============================

=====Starting from node 1=====
Distance to node 0 from node 1 = 3
Distance to node 1 from node 1 = 0
Distance to node 2 from node 1 = 5
Distance to node 3 from node 1 = 5
Distance to node 4 from node 1 = 3
Distance to node 5 from node 1 = 4
Distance to node 6 from node 1 = 7
Distance to node 7 from node 1 = 6
Distance to node 8 from node 1 = 6
Distance to node 9 from node 1 = 2
==============================

=====Starting from node 2=====
Distance to node 0 from node 2 = 4
Distance to node 1 from node 2 = 5
Distance to node 2 from node 2 = 0
Distance to node 3 from node 2 = 6
Distance to node 4 from node 2 = 8
Distance to node 5 from node 2 = 1
Distance to node 6 from node 2 = 5
Distance to node 7 from node 2 = 1
Distance to node 8 from node 2 = 6
Distance to node 9 from node 2 = 7
==============================

=====Starting from node 3=====
Distance to node 0 from node 3 = 2
Distance to node 1 from node 3 = 5
Distance to node 2 from node 3 = 6
Distance to node 3 from node 3 = 0
Distance to node 4 from node 3 = 5
Distance to node 5 from node 3 = 5
Distance to node 6 from node 3 = 6
Distance to node 7 from node 3 = 7
Distance to node 8 from node 3 = 10
Distance to node 9 from node 3 = 7
==============================

=====Starting from node 4=====
Distance to node 0 from node 4 = 6
Distance to node 1 from node 4 = 3
Distance to node 2 from node 4 = 8
Distance to node 3 from node 4 = 5
Distance to node 4 from node 4 = 0
Distance to node 5 from node 4 = 7
Distance to node 6 from node 4 = 10
Distance to node 7 from node 4 = 9
Distance to node 8 from node 4 = 9
Distance to node 9 from node 4 = 5
==============================

=====Starting from node 5=====
Distance to node 0 from node 5 = 3
Distance to node 1 from node 5 = 4
Distance to node 2 from node 5 = 1
Distance to node 3 from node 5 = 5
Distance to node 4 from node 5 = 7
Distance to node 5 from node 5 = 0
Distance to node 6 from node 5 = 4
Distance to node 7 from node 5 = 2
Distance to node 8 from node 5 = 5
Distance to node 9 from node 5 = 6
==============================

=====Starting from node 6=====
Distance to node 0 from node 6 = 4
Distance to node 1 from node 6 = 7
Distance to node 2 from node 6 = 5
Distance to node 3 from node 6 = 6
Distance to node 4 from node 6 = 10
Distance to node 5 from node 6 = 4
Distance to node 6 from node 6 = 0
Distance to node 7 from node 6 = 6
Distance to node 8 from node 6 = 9
Distance to node 9 from node 6 = 9
==============================

=====Starting from node 7=====
Distance to node 0 from node 7 = 5
Distance to node 1 from node 7 = 6
Distance to node 2 from node 7 = 1
Distance to node 3 from node 7 = 7
Distance to node 4 from node 7 = 9
Distance to node 5 from node 7 = 2
Distance to node 6 from node 7 = 6
Distance to node 7 from node 7 = 0
Distance to node 8 from node 7 = 7
Distance to node 9 from node 7 = 8
==============================

=====Starting from node 8=====
Distance to node 0 from node 8 = 8
Distance to node 1 from node 8 = 6
Distance to node 2 from node 8 = 6
Distance to node 3 from node 8 = 10
Distance to node 4 from node 8 = 9
Distance to node 5 from node 8 = 5
Distance to node 6 from node 8 = 9
Distance to node 7 from node 8 = 7
Distance to node 8 from node 8 = 0
Distance to node 9 from node 8 = 4
==============================

=====Starting from node 9=====
Distance to node 0 from node 9 = 5
Distance to node 1 from node 9 = 2
Distance to node 2 from node 9 = 7
Distance to node 3 from node 9 = 7
Distance to node 4 from node 9 = 5
Distance to node 5 from node 9 = 6
Distance to node 6 from node 9 = 9
Distance to node 7 from node 9 = 8
Distance to node 8 from node 9 = 4
Distance to node 9 from node 9 = 0
==============================

→ 실제 최단 거리와 일치

음의 가중치 그래프에서 각 점에서 최단 거리

=====Starting from node 0=====
Distance to node 0 from node 0 = 0
Distance to node 1 from node 0 = 0
Distance to node 2 from node 0 = -3
Distance to node 3 from node 0 = 2
Distance to node 4 from node 0 = -3
Distance to node 5 from node 0 = -4
Distance to node 6 from node 0 = -8
Distance to node 7 from node 0 = -4
Distance to node 8 from node 0 = 1
Distance to node 9 from node 0 = 2
==============================

=====Starting from node 1=====
Distance to node 0 from node 1 = -4
Distance to node 1 from node 1 = 0
Distance to node 2 from node 1 = -3
Distance to node 3 from node 1 = -2
Distance to node 4 from node 1 = -7
Distance to node 5 from node 1 = -4
Distance to node 6 from node 1 = -8
Distance to node 7 from node 1 = -4
Distance to node 8 from node 1 = 1
Distance to node 9 from node 1 = 2
==============================

=====Starting from node 2=====
Distance to node 0 from node 2 = 0
Distance to node 1 from node 2 = -3
Distance to node 2 from node 2 = 0
Distance to node 3 from node 2 = -5
Distance to node 4 from node 2 = 0
Distance to node 5 from node 2 = 1
Distance to node 6 from node 2 = -3
Distance to node 7 from node 2 = -1
Distance to node 8 from node 2 = 3
Distance to node 9 from node 2 = -1
==============================

=====Starting from node 3=====
Distance to node 0 from node 3 = -6
Distance to node 1 from node 3 = -2
Distance to node 2 from node 3 = -5
Distance to node 3 from node 3 = 0
Distance to node 4 from node 3 = -5
Distance to node 5 from node 3 = -6
Distance to node 6 from node 3 = -10
Distance to node 7 from node 3 = -6
Distance to node 8 from node 3 = -1
Distance to node 9 from node 3 = 0
==============================

=====Starting from node 4=====
Distance to node 0 from node 4 = -3
Distance to node 1 from node 4 = 0
Distance to node 2 from node 4 = -3
Distance to node 3 from node 4 = -5
Distance to node 4 from node 4 = 0
Distance to node 5 from node 4 = -4
Distance to node 6 from node 4 = -8
Distance to node 7 from node 4 = -4
Distance to node 8 from node 4 = 1
Distance to node 9 from node 4 = 2
==============================

=====Starting from node 5=====
Distance to node 0 from node 5 = -1
Distance to node 1 from node 5 = -4
Distance to node 2 from node 5 = 1
Distance to node 3 from node 5 = -6
Distance to node 4 from node 5 = -1
Distance to node 5 from node 5 = 0
Distance to node 6 from node 5 = -4
Distance to node 7 from node 5 = 0
Distance to node 8 from node 5 = 2
Distance to node 9 from node 5 = -2
==============================

=====Starting from node 6=====
Distance to node 0 from node 6 = -5
Distance to node 1 from node 6 = -8
Distance to node 2 from node 6 = -3
Distance to node 3 from node 6 = -10
Distance to node 4 from node 6 = -5
Distance to node 5 from node 6 = -4
Distance to node 6 from node 6 = 0
Distance to node 7 from node 6 = -4
Distance to node 8 from node 6 = -2
Distance to node 9 from node 6 = -6
==============================

=====Starting from node 7=====
Distance to node 0 from node 7 = -1
Distance to node 1 from node 7 = -4
Distance to node 2 from node 7 = -1
Distance to node 3 from node 7 = -6
Distance to node 4 from node 7 = -1
Distance to node 5 from node 7 = 0
Distance to node 6 from node 7 = -4
Distance to node 7 from node 7 = 0
Distance to node 8 from node 7 = 2
Distance to node 9 from node 7 = -2
==============================

=====Starting from node 8=====
Distance to node 0 from node 8 = 4
Distance to node 1 from node 8 = 1
Distance to node 2 from node 8 = 6
Distance to node 3 from node 8 = -1
Distance to node 4 from node 8 = 4
Distance to node 5 from node 8 = 5
Distance to node 6 from node 8 = 1
Distance to node 7 from node 8 = 5
Distance to node 8 from node 8 = 0
Distance to node 9 from node 8 = 4
==============================

=====Starting from node 9=====
Distance to node 0 from node 9 = -2
Distance to node 1 from node 9 = 2
Distance to node 2 from node 9 = -1
Distance to node 3 from node 9 = 0
Distance to node 4 from node 9 = -5
Distance to node 5 from node 9 = -2
Distance to node 6 from node 9 = -6
Distance to node 7 from node 9 = -2
Distance to node 8 from node 9 = 3
Distance to node 9 from node 9 = 0
==============================

Process finished with exit code 0

→ 음의 가중치 그래프에서는 최단 거리 계산 불가

📌 Bellman-Ford Algorithm

Question. Bellman-Ford 알고리즘을 구현하고 PDF에 나온 예제를 input으로 넣어 점검하여라

📍 Implement

Code

import java.util.Arrays;

public class BellmanFord {

    private int[] distance;
    private final Graph graph;

    private final int INFINITY = Integer.MAX_VALUE;

    // Constructor
    public BellmanFord(Graph graph) {
        this.graph = graph;
    }

    // Bellman-Ford Algorithm
    public void algorithm(int start) {
        int size = graph.size();
        int[][] weights = graph.getWeights();
        init(start, size);
        main(size, weights);
    }

    // Init
    private void init(int start, int size) {
        distance = new int[size];
        Arrays.fill(distance, INFINITY);
        distance[start] = 0;
    }

    // Main
    private void main(int size, int[][] weights) {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (weights[i][j] != INFINITY) {
                    distance[j] = Math.min(distance[j], distance[i] + weights[i][j]);
                }
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < graph.size(); i++) {
            builder.append("Distance to node ").append(i).append(" = ")
                    .append(distance[i]).append("\n");
        }
        return builder.toString();
    }
}

📍 Example

Graph

Untitled

Testing

Distance to node 0 = 0
Distance to node 1 = -1
Distance to node 2 = 2
Distance to node 3 = -2
Distance to node 4 = 1

📌 Greedy Algorithm

Question. Greedy 알고리즘에 대해 조사하고 예를 들어 설명하여라

📍 About

What is greedy algorithm

Greedy algorithm은 가능한 해들 중에서 최적해를 찾는 알고리즘이다. 하지만 한 번 선택한 최적해를 번복하지 않기 때문에 근시안적인 알고리즘이다. 그렇기 때문에 단순하고 제한적인 문제만을 해결할 수 있다.

Example

동전 거스름돈 문제

가장 대표적인 예시가 동전 거스름돈 문제이다. 남은 액수를 초과하지 않는 선에서 최대 액수 동전을 지불한다고 했을 때 최대 액수의 동전붙터 차례대로 최대로 지불한다. 100, 70, 50, 10원으로 190원을 지불한다고 했을 때 우선 100원을 지불한다. 나머지 90원에서 70원을 지불하고 또 남은 20원은 10원 2개로 지불한다. 최종적으로 100, 70, 10, 10원을 지불한다. 하지만 실제 최적해는 70, 70, 50원 3개로 지불하는 것이다. 여기서 근시안적인 특징을 확인할 수 있다.
부분 배낭 문제

또 다른 예시로는 부분 배낭 문제가 있다. 배낭 문제는 n개의 물건은 가치와 무게가 있으며 가방에 무게 제한이 있을 때 최대한의 가치를 넣는 것이다. 부분 배낭 문제는 물건을 부분 적으로 담을 수 있는 경우이다. 가치가 높은 것부터 차례대로 가방에 보관하며 담을 수 있는 무게가 부족할 떄는 최대 가치를 나누어서 보관한다.

📌 Maze

Question. 1000 x 1000 배열의 미로찾기 게임에서 DFS, BFS, Dijkstra 알고리즘의 속도 비교와 원인 정리

→ 시간 부족으로 우선 다익스트라와 1000 x 1000 크기의 미로는 제외하였습니다.

Point

Code

public class Point {
    private final int height, width;

    public Point(int height, int width) {
        this.height = height;
        this.width = width;
    }

    public int getHeight() {
        return height;
    }

    public int getWidth() {
        return width;
    }
}

Maze

Code

import java.util.LinkedList;
import java.util.Queue;

public class Maze {

    private final int height, width;
    private final boolean[][] maze;
    private boolean[][] visited;

    public Maze(int height, int width, boolean[][] maze) {
        this.height = height;
        this.width = width;
        this.maze = maze;
    }

    public Maze(int height, int width) {
        this.height = height;
        this.width = width;
        maze = new boolean[height + 2][width + 2];
    }

    private void init() {
        for (int h = 1; h <= height; h++)
            for (int w = 1; w <= width; w++)
                maze[h][w] = (int) (Math.random() * 2) == 1;
        maze[1][1] = maze[height][width] = true;
    }

    private void findBy(int type) {
        visited = new boolean[height + 2][width + 2];
        try {
            switch (type) {
                case 0:
                    dfs(1, 1);
                    System.out.println("목적지를 찾을 수 없습니다.");
                    break;
                case 1:
                    Queue<Point> queue = new LinkedList<>();
                    queue.add(new Point(1, 1));
                    bfs(queue);
                    System.out.println("목적지를 찾을 수 없습니다.");
                    break;
                default:
                    System.out.println("Wrong Input");
            }
        } catch (Exception e) {
            System.out.println("목적지에 도착하였습니다.");
        }
    }

    private void dfs(int height, int width) throws Exception {
        if (height == this.height && width == this.width)
            throw new Exception("Finish");
        if (!visited[height][width] && maze[height][width]) {
            visited[height][width] = true;
            dfs(height + 1, width);
            dfs(height - 1, width);
            dfs(height, width + 1);
            dfs(height, width - 1);
        }
    }

    private void bfs(Queue<Point> queue) throws Exception {
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int height = point.getHeight();
            int width = point.getWidth();
            if (height == this.height && width == this.width)
                throw new Exception("Finish");
            if (!visited[height][width] && maze[height][width]) {
                visited[height][width] = true;
                queue.add(new Point(height + 1, width));
                queue.add(new Point(height - 1, width));
                queue.add(new Point(height, width + 1));
                queue.add(new Point(height, width - 1));
            }
        }
    }

    public static void main(String[] args) {
        Maze maze = new Maze(3, 6, new boolean[][]{
                {false, false, false, false, false, false, false, false},
                {false, true, false, false, false, false, false, false},
                {false, true, false, false, false, false, false, false},
                {false, true, true, true, true, true, true, false},
                {false, false, false, false, false, false, false, false}
        });
        new Thread(() -> maze.findBy(0)).start();
        new Thread(() -> maze.findBy(1)).start();
    }
}

Maze S X X X X X O X X X X X O O O O O E
Result 목적지에 도착하였습니다.
목적지에 도착하였습니다.

📌 Problem Solving

📍 Network

https://programmers.co.kr/learn/courses/30/lessons/43162

Code

class Solution {

    private int n;
    private int[][] computers;
    private boolean[] visited;
    private int count = 0;

    private void find(int num) {
        for (int i = 0; i < n; i++) {
            if (!visited[i] && computers[num][i] == 1) {
                visited[i] = true;
                find(i);
            }
        }
    }

    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        this.computers = computers;
        this.n = n;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                find(i);
                count++;
            }
        }

        return count;
    }
}

📍 Change Word

https://programmers.co.kr/learn/courses/30/lessons/43163

Code

class Solution {
    private boolean[] visited;
    private int step = 0;

    private void dfs(String from, String target, String[] words, int count) {
        if (from.equals(target)) {
            step = count;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (visited[i]) continue;

            int cnt = 0;
            for (int j = 0; j < from.length(); j++)
                if (from.charAt(j) == words[i].charAt(j))
                    cnt++;

            if (cnt == from.length() - 1) {
                visited[i] = true;
                dfs(words[i], target, words, count + 1);
                visited[i] = false;
            }
        }
    }

    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        dfs(begin, target, words, 0);
        return step;
    }
}

📍 Travel Path

https://programmers.co.kr/learn/courses/30/lessons/43164

Code

📍 Target Number

https://programmers.co.kr/learn/courses/30/lessons/43165

Code

class Solution {

    private int[] numbers;
    private int target;
    private int count = 0;

    private void calc(int idx, int sum) {
        if (idx == numbers.length) {
            count += sum == target ? 1 : 0;
        } else {
            calc(idx + 1, sum + numbers[idx]);
            calc(idx + 1, sum - numbers[idx]);
        }
    }

    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        calc(0, 0);
        return count;
    }
}

📍 Rank

https://programmers.co.kr/learn/courses/30/lessons/49191

Code

class Solution {

    private int size;
    private int[][] graph;

    private void init(int[][] results) {
        for (int i = 0; i < results.length; i++) {
            int winner = results[i][0];
            int loser = results[i][1];
            graph[winner - 1][loser - 1] = 1;
            graph[loser - 1][winner - 1] = -1;
        }
    }

    private void floyd() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    if (graph[i][k] == 1 && graph[k][j] == 1) {
                        graph[i][j] = 1;
                        graph[j][i] = -1;
                    }
                    if (graph[i][k] == -1 && graph[k][j] == -1) {
                        graph[i][j] = -1;
                        graph[j][i] = 1;
                    }
                }
            }
        }
    }

    private int count() {
        int count = 0;
        for (int i = 0; i < size; i++) {
            int cnt = 0;
            for (int j = 0; j < size; j++)
                if (graph[i][j] != 0)
                    cnt++;
            if (cnt == size - 1)
                count++;
        }
        return count;
    }

    public int solution(int size, int[][] results) {
        this.size = size;
        graph = new int[size][size];
        init(results);
        floyd();
        return count();
    }
}

📍 Farest Node

https://programmers.co.kr/learn/courses/30/lessons/49189

Code

import java.util.LinkedList;
import java.util.Queue;

class Solution {

    private boolean[] visited;
    private int[] distance;
    private boolean[][] graph;
    private int depth;

    static class Vertex {
        int num;
        int depth;

        Vertex(int num, int depth) {
            this.num = num;
            this.depth = depth;
        }
    }

    private void init(int n, int[][] edge) {
        visited = new boolean[n + 1];
        distance = new int[n + 1];
        graph = new boolean[n + 1][n + 1];

        for (int[] ints : edge) {
            int nodeA = ints[0], nodeB = ints[1];
            graph[nodeA][nodeB] = graph[nodeB][nodeA] = true;
        }
    }

    private void bfs() {
        Queue<Vertex> queue = new LinkedList<>();
        queue.add(new Vertex(1, 0));
        visited[1] = true;

        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            for (int i = 1; i < visited.length; i++)
                if (!visited[i] && graph[vertex.num][i]) {
                    visited[i] = true;
                    distance[i] = depth = vertex.depth + 1;
                    queue.add(new Vertex(i, depth));
                }
        }
    }

    private int count() {
        int count = 0;
        for (int i = 1; i < distance.length; i++)
            if (distance[i] == depth)
                count++;
        return count;
    }

    public int solution(int n, int[][] edge) {
        init(n, edge);
        bfs();
        return count();
    }
}

📍 Disk Controller

https://programmers.co.kr/learn/courses/30/lessons/42627

Code

codesver

Hello, Devs!

이전 포스트

Job Boot Camp : Week 01 Report

다음 포스트

Job Boot Camp : Week 02 Report

Job Boot Camp

📌 Max Heap

📍 Implement

📌 Dijkstra Algorithm

📍 Implement

Graph

Dijkstra

📍 Testing

Graph

Result

📌 Bellman-Ford Algorithm

📍 Implement

📍 Example

Graph

Testing

📌 Greedy Algorithm

📍 About

What is greedy algorithm

Example

📌 Maze

Point

Maze

📌 Problem Solving

📍 Network

📍 Change Word

📍 Travel Path

📍 Target Number

📍 Rank

📍 Farest Node

📍 Disk Controller

Job Boot Camp : Week 01 Report

Job Boot Camp : Week 03 Lecture

0개의 댓글