심플하고 차분하게

|  동적계획법이란?

- 복잡한 문제를 여러 개의 간단한 문제로 분리하여 해결하는 방법

- 원리 및 구현 방법

1) 큰 문제를 부분적으로 분리하여 분석한다

--> 부분적인 문제의 결과값은 항상 동일해야한다.

2) 1)을 통해 알게된 규칙을 통해 점화식을 생성한다.

3) 기존 배열과 dp배열을 어떻게 만들지 구상하고

4) 아래 두 가지 방법 중 적절한 구현 방법에 따라 수도 코드를 작성한다. 

타뷸레이션	= 바텀-업	- for문을 사용하여 구현
메모이제이션	= 탑-다운	* 이미지 출처 : 나무위키 - 재귀를 사용하여 구현

|  피보나치를 통해 보는 동적 계획법

- 점화식을 통해 재귀로 푼 피보나치 문제 풀이는 아래와 같았다.

// 피보나치 수열
// 재귀 (일반풀이 방법) - O(n^2), 계산했던 부분도 다시 계산
int fibonachi(int n) {
    if (n < 2) {
        return n;
    } else {
        return fib(n - 2) + fib(n - 1);
    }
}

- 타뷸레이션 방식으로 이를 풀게 되면, 1 1 2 3 5 8.. 순으로 데이터를 넣고 조회한다.

// 타뷸레이션 방식 - O(n)
int fibo2(int n) {
	// 재활용할 메모리 공간
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    
    for (int i = 1; i <= n; i++){
    	dp[i] = dp[i - 2] + dep[i - 1];
    }
    
    return dp[n];
}

- 메모이제이션을 사용하게 되면, Top-down 방식으로 재귀를 호출하는데,

  첫번째 방식과의 차이는 이미 확인한 데이터는 다시 하위로 깊이를 내려가 풀이 하지 않는다는 것이 다르다.

// 메모이제이션 방식 - O(n)
int[] dp = new int[8];
int fibo2(int n) {

    if (n <= 2) {
    	return 1;
    } 
    
    if (dp[n] != 0) {
    	return dp[n];
    }
    
    dp[n] = fibo2(n - 2) + fibo2(n - 1);
    
    return dp[n];
}

|  백준 문제풀이

D[i] = D[i - 1] + 1
if (2의 배수) D[i / 2] + 1이 D[i]보다 작으면 변경
if (3의 배수) D[i / 3] + 1이 D[i]보다 작으면 변경

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Ex1463 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N : 구하고자 하는 수
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        dp[1] = 0;

        // * 규칙이 반복되는 구간은 2부터
        // for (i : 2 ~ N) {
        //    D[i] = D[i - 1] + 1 // 1을 뺀 점화시
        //    if (2의 배수) D[i / 2] + 1이 D[i]보다 작으면 변경
        //    if (3의 배수) D[i / 3] + 1이 D[i]보다 작으면 변경
        // } 
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;

            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }

            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

        // 출력
        System.out.println(dp[N]);
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Ex14501 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 개의 스케줄을 각각의 일차원 배열에 받는다.
        int N = Integer.parseInt(br.readLine());

        // D 점화식 배열
        int[] D = new int[N + 2];

        // T 기간 배열
        int[] T = new int[N + 1];

        // P 수입 배열
        int[] P = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        // 터뷸레이션을 사용해서 D를 구한다.
        // D[i] = i날짜부터 n+1(퇴사일)까지 벌수 있는 최대 수익
        // for (i : N ~ 1){
        //    if (i+T[i]가 퇴사일보다 크면) D[i] = D[i + 1]
        //    if (i+T[i]가 퇴사일보다 크지 않으면) D[i] = Math.max(D[i + 1], P[i] + D[i + T[i]])
        // }
        for (int i = N; i >= 1; i--) {
            if (i + T[i] > N + 1) {
                D[i] = D[i + 1];
            } else {
                D[i] = Math.max(D[i + 1], D[i + T[i]] + P[i]);
            }
        }

        // 출력
        // D[1]
        System.out.println(D[1]);
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Ex2193 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        // D 배열을 만든다 (2차원 배열)
        // dp[1][0] = 0, dp[1][1] = 1 초기화
        long[][] dp = new long[N + 1][2];
        dp[1][0] = 0;
        dp[1][1] = 1;

        // for (i : 2 ~ N) {
        //    dp[i][0] = dp[i - 1][0] + dp[i - 1][1] // 0은 0이나 1 뒤에 붙일 수 있다.
        //    dp[i][1] = dp[i - 1][0] // 1은 0 뒤에만 붙일 수 있다.
        // }
        for (int i = 2; i <= N; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
            dp[i][1] = dp[i - 1][0];
        }

        System.out.println(dp[N][0] + dp[N][1]);
    }
}

[ 출처 및 참조 ]

- 부트 캠프 강의를 들은 후 정리한 내용입니다.

- [Do it! 알고리즘 코딩 테스트 - 자바 편] 

|  모듈러 산술

- 모듈러 (=mod = %)는 덧셈, 뺄셈, 곱셈에 있어서 아래와 같은 산술을 할 수 있는 특징이 있다.

- 알고리즘 문제를 풀다보면 애매하게 정수 Max값을 넘을랑 말랑 하는 데이터가 있기도 한데,

  그럴 때 이 모듈러 산술을 고려해서 문제를 풀면 굳이 Long 타입 변수를 쓰지 않아도 Int만으로 충분히 풀이가 가능하다.

(a + b) % C = (a % C + b % C) % C
(a - b) % C = (a % C - b % C) % C
(a * b) % C = (a % C * b % C) % C

|  참고할 만한 문제

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

[ 참고 ]

https://developer-mac.tistory.com/84

https://sskl660.tistory.com/75

|  분할정복이란?

- 폰노이만 구조를 만든 그 폰노이만에 의해 소개된 알고리즘

- 간략하게 말하면, 큰 문제를 작은 단위로 쪼갠 후 다시 조합하여 문제를 해결하는 방법을 말한다.

분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다

*출처 : 나무위키

|  분할정복 과정

1. 문제를 하나 이상의 작은 단위로 분할

2. 작은 단위에서 부분적인 해결

3. 부분들의 해결을 조합해 전체 문제의 해답을 찾는다.

function F(x):
  if F(x)가 간단 then:
    return F(x)를 계산한 값
  else:
    x 를 x1, x2로 분할
    F(x1)과 F(x2)를 호출
    return F(x1), F(x2)로 F(x)를 구한 값
    
* 출처 : 나무위키

|  장단점

|  예시

분할정복의 예시로 자주 거론되는 것으로 아래 네 가지가 있다. 

이 중에서 내 단계에서 언급하기 쉬워 보이는 1~3의 알고리즘만 적어보려고 한다.

1. 합병 정렬

2. 퀵소트

3. 카라추바 알고리즘

4. 고속 푸리에 변환

1. 합병정렬

- 분할정복과 투포인터의 특성을 사용해서 만들어진 정렬이라 볼 수 있을 것 같다.

- 1) 먼저 배열의 범위를 투 포인터를 통해 분할하여 지정한 후에,

- 2) 작은 범위에서 데이터를 비교하여 정렬을 하고

- 3) 작은 범위를 조합하여 전체 정렬을 이루는 과정 

void mergeSort(int[] arr, int[] tmp, int left, int right){
	if (left < right) {
    	int mid = (left + right) / 2;
        // mid를 기준으로 배열을 분할한다.
        mergeSort(arr, tmp, left, mid);
        mergeSort(arr, tmp, mid + 1, right);
        // mid를 기준으로 배열을 조합한다.
        merge(arr, tmp, left, right, mid);
    }
}

void merge(int[] arr, int[] tmp, int left, int right, int mid){
    // mid를 기준으로 좌/우 포인터, 
    // index포인터를 준비하고
    int l = left;
    int r = mid + 1; 
    int idx = left;
    
    // 좌/우 포인터를 비교하여 tmp에 오름차순으로 저장
    // 적어도 두 포인터 중 하나가 범위 내에 있을 때에
    while (l <= mid || r <= right){
    	// 조건1 : 모든 포인터가 범위내에 있다면
        if (l <= mid && r <= right){
        	// 두 포인터의 데이터를 비교해서 
            // 더 작은 데이터를 tmp에 넣고, 포인터를 하나 증가한다.
            if (arr[l] <= arr[r]){
            	tmp[idx++] = arr[l++];
            } else {
            	tmp[idx++] = arr[r++];
            }
        } 
        // 조건2 : left포인터만 범위내에 있다면
        else if (l <= mid && r > right){
        	tmp[idx++] = arr[l++];
        }
        // 조건3 : right포인터만 범위내에 있다면
        else {
        	tmp[idx++] = arr[r++];
        }
    }
    
    // tmp의 데이터를 arr에 옮긴다.
    for (int i = left; i <= right; i++){
    	arr[i] = tmp[i];
    }
}

2. 퀵소트

- 피봇이라는 기준값을 토대로 투포인터와 분할정복을 활용한 정렬 알고리즘이다.

- 1) 먼저 피봇값이라는 기준값을 지정하고 반정렬

- 2) 피봇값을 기준으로 배열을 분할

- 3) 분할된 배열을 부분적으로 정렬

void quickSort(int[] arr, int left, int right){
	// 탈출문
    if (left >= right) {
    	return;
    }
    
    // 피봇값을 지정
    int pivot = partition(arr, left, right);
    
    // 피봇값을 기준으로 배열을 분할
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

void int partition(int[] arr, int left, int right){
	// 투 포인터와 피봇값 지정
    int l = left;
    int r = right;
    int pivot = arr[left];
    
    // 피봇값을 기준으로 양 끝 포인터를 올리거나 내려준다
    while(l < r) {
    	while (arr[r] > pivot && l < r) {
        	r--;
        }
        
        while (arr[l] <= pivot && l < r) {
        	l++;
        }
        
        swap(arr, l, r);
    }
    // 기존 피봇값 위치 데이터와 피봇값을 교환
    swap(arr, left, l);
    
    return l;
}

3. 카라추바 알고리즘

- 카라추바라는 사람이 1960년에 만든 분할정복 알고리즘으로, 

- 초등학교 곱셈 공식에서 배웠던 각 자릿수를 곱하는 방식을 응용해 만든 알고리즘이다.

- 알고리즘 구현의 단계는 아래와 같다.

1. z0 = a * c
2. z1 = b * d
3. z2 = (a + b)(c + d)
4. z3 = z0 - ac - bd
5. (z0 * 10^n) + (z3 * 10^(n/2)) + z1

- 아래 코드 외에 아예 ArrayList를 사용해서 각 자릿수를 저장하는 방식 또한 있는데, 

  굉장히 복잡하기 때문에 관련된 코드는 검색을 통해 복사하여 사용하는 편이 좋을 것 같다.

** 자바에는 BigInteger라는 큰 수를 다루는 객체가 따로 있다.

  (큰 수의 곱셈은 이 객체의 multiply() 메소드를 쓰는 것이 코드를 가독성 있게 짜기에는 더 좋아 보인다.) 

public static long karatsuba(long x, long y) {
    // 범위가 작은 경우
    if (x <= 50 && y <= 50) {
        return x * y;
    }

    // a와 b의 자릿수
    int numXLen = (int)Math.log10(x);
    int numYLen = (int)Math.log10(y);

    // a와 b의 자릿수 중에 더 큰 자릿수를 선택
    int maxLen = Math.max(numXLen, numYLen); // ex 1234 -> 4

    // 분할한 자릿수
    Integer halfMaxLen = (maxLen / 2) + (maxLen % 2); // ex 1234 -> 2

    // Multiplier : 곱할 10^n
    long halfMaxLenTen = (long)Math.pow(10, halfMaxLen); // ex 1234 -> 10^2

    // 분할한 수들을 구한다.
    long a = x / halfMaxLenTen;
    long b = x % halfMaxLenTen;
    long c = y / halfMaxLenTen;
    long d = y % halfMaxLenTen;

    // 4단계에 따라 각 수들을 곱하고 더한다.
    // 1. a * c
    // 2. b * d
    // 3. (a+b)(c+d)
    // 4. (3)에서 (1), (2)를 뺀다
    // 5. (1) x halfMaxLen + (2) + (4) x (halfMaxLen / 2)
    long z0 = karatsuba(a, c);
    long z1 = karatsuba(b, d);
    long z2 = karatsuba(a + b, c + d);
    long z3 = z2 - z1 - z0;

    long res = (z0 * (long)Math.pow(10, halfMaxLen * 2)) + (z3 * (long)Math.pow(10, halfMaxLen)) + z1;
    return res;
}

|  백준 문제

- 백준의 분할 정복에 대한 문제는 사실상 재귀 문제와 별반 다를게 없었다.

- 그만큼 재귀와 분할정복이 서로 땔래야 땔 수 없는 관계라는 것을 의미하는 듯 하다.

https://www.acmicpc.net/workbook/view/798

[ 출처 및 참조 ]

- 부트 캠프 강의를 들은 후 정리한 내용입니다.

- [Do it! 알고리즘 코딩 테스트 - 자바 편] 

- 나무위키,  https://namu.wiki/w/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://www.geeksforgeeks.org/java-program-to-implement-the-karatsuba-multiplication-algorithm/

|  그리디란?

- 그리디 알고리즘은, 매 선택에서 지금 이 순간 가장 최선이라 생각되는 답을 선택해 결과를 도출하는 것을 말한다.

- 여기서 Greedy을 직역하면 '탐욕'을 뜻한다.

- 왜 '탐욕'이라는 말을 쓸까?

  그건 지금 이 순간의 부분적인 최적해가 항상 종합적인 최적해는 아닐 수 있음에도,

  욕심쟁이와 같이 지금 보는 이 부분적인 선택이 전체의 최선이라 단정짓기 때문이다.

  rf. 여러 개의 도시가 연결된 도로가 있고, 그 도로 간에 이동 거리가 각각 다른 상황에서

      가장 이동거리가 짧은 거리를 찾아야한다고 할 때, 그리디를 쓰면 가장 짧은 도로들을 선택하는 게 될 수 있다.

- 정확함 보다는 적당히 맞는 답을 찾을 때 좋은 알고리즘이다. 따라서, 그리디 알고리즘을 근사 알고리즘으로도 부른다.

- 언제 쓰는 게 좋을까?

   탐욕 선택 속성, 최적 부분 구조 특정을 가진 문제를 해결하는 데에 강점이 있다.

   ex. 서울에서 대구를 거쳐 부산까지 가는 최단 경로 : 서울~대구 최단 경로 + 대구 ~ 부산 최단 경로

- 그럼 그리디로 풀지 못하는 문제들은 뭘로 풀어야 하지? 

  - 그리디로 풀지 못하는 문제들을 나무위키에서는 아래와 같이 두 가지를 소개했다.

  - 두 문제 모두 DP(동적 계획법)으로 풀 수 있는데, 두 가지 모두 차후 풀이 후 정리해보려고 한다.

- 그리디 알고리즘의 풀이 순서

|  대표적인 그리디 문제 

|  그리디 문제집

https://www.acmicpc.net/step/33

[ 참고 및 출처 ]

부트캠프 강의 후 정리

[Do it 알고리즘 코딩 테스트 - 자바 편]

나무위키

|  탐색이란?

주어진 데이터들 중에서 원하는 데이터를 찾아내는 알고리즘

|  탐색의 종류

* DFS, BFS 모두 간선의 갯수가 적을 때에, 인접 리스트를 쓰는게 유리하다.

1. DFS (깊이 우선 탐색)

DFS란, 루트에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

[출처] https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

- 참조한 블로그에서는 미로를 탐색하는 것을 이야기했는데, 미로의 여러 갈랫길 중 첫번째 길만 쫒아가다가 다시 돌아와(backtracking) 방문하지 않은 곳을 탐색하여, 결국 모든 곳을 가는 것을 DFS라고 했다.

- 하나의 노드 A와 인접한 노드가 B, C가 있다고 할 때 먼저 B의 분기(인접한 노드들)를 모두 마쳐야만, C를 갈 수 있다.

- 트리의 level-order을 제외한 나머지 순회들과의 차이점은 어떤 노드를 방문했는지를 방문 배열을 통해 검사한다는 것.

(1) 구현 

- 백준의 아래 문제를 통해 한 번 구현해보았다.

[1] 먼저 자료구조를 초기화한다. : 정점/간선 갯수나, 인접리스트, 방문배열은 전역으로 빼주었다.

public class Ex11724 {

    static int N;
    static int M;
    static List<List<Integer>> graph;
    static boolean[] visited;
    static int cnt;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 인접 리스트 그래프 초기화
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        // 방문 배열 초기화
        visited = new boolean[N + 1];

        cnt = 0;
    }
}

[2] 문제에서 요구하는 연결망의 갯수 구하는 코드를 넣는다.

- 이 문제는 프로그래머스의 '네트워크' 문제와도 유사했는데, 분리된 연결망을 구하는 문제였다.

> 분기를 확인하기 위한 코드

// 2. dfs
for (int i = 1; i <= N; i++) {
    if (!visited[i]) {
        dfs_stack(i);
        cnt++;
    }
}

System.out.println(cnt);

> 예외 상황 : 노드가 하나밖에 없고 간선이 없는 경우 - 네트웍은 하나다.

// 노드가 하나밖에 없고 간선이 없어도 네트웍은 하나로 치부
if (N == 1 && M == 0) {
    System.out.println(1);
    return;
}

[3] 본격적인 dfs를 짜기

[3-1] 재귀 방식의 dfs

public static void dfs(int root) {

    // 루트 방문 체크
    visited[root] = true;

    // 인접한 노드들 중 방문하지 않은 곳을 방문
    for (int i = 0; i < graph.get(root).size(); i++) {

        int adjNode = graph.get(root).get(i);

        if (!visited[adjNode]) {
            dfs(adjNode);
        }
    }

}

[3-2] 스택 방식의 dfs

public static void dfs_stack(int start) {

    Stack<Integer> stack = new Stack<>();
    visited[start] = true;
    stack.push(start);

    while (!stack.isEmpty()) {
        int curNode = stack.pop();

        for (int i = 0; i < graph.get(curNode).size(); i++) {
            int adjNode = graph.get(curNode).get(i);

            if (!visited[adjNode]) {
                stack.push(adjNode);
                visited[adjNode] = true;
            }
        }
    }
}

[ 전체 코드 - 더보기 ]

package graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;


public class Ex11724 {

    static int N;
    static int M;
    static List<List<Integer>> graph;
    static boolean[] visited;

    static int cnt;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        if (N == 1 && M == 0) {
            System.out.println(1);
            return;
        }

        // 1. 시작 노드를 정한 후 사용할 자료구조 초기화
        // 인접 리스트 그래프 초기화
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        // 방문 배열 초기화
        visited = new boolean[N + 1];

        cnt = 0;

        // 2. dfs
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                dfs_stack(i);
                cnt++;
            }
        }

        System.out.println(cnt);
    }

    public static void dfs(int root) {

        // 루트 방문 체크
        visited[root] = true;

        // 인접한 노드들 중 방문하지 않은 곳을 방문
        for (int i = 0; i < graph.get(root).size(); i++) {

            int adjNode = graph.get(root).get(i);

            if (!visited[adjNode]) {
                dfs(adjNode);
            }
        }

    }

    public static void dfs_stack(int start) {

        Stack<Integer> stack = new Stack<>();
        visited[start] = true;
        stack.push(start);

        while (!stack.isEmpty()) {
            int curNode = stack.pop();

            for (int i = 0; i < graph.get(curNode).size(); i++) {
                int adjNode = graph.get(curNode).get(i);

                if (!visited[adjNode]) {
                    stack.push(adjNode);
                    visited[adjNode] = true;
                }
            }
        }
    }

}

(2) 시간 복잡도

- DFS는 그래프의 정점의 수(V)와 간선의 수(E)를 통해 시간 복잡도를 표현하는데,

- 인접 행렬을 사용하는 경우, 행으로는 전체 정점(V)을, 열로는 인접한 정점과의 연결 여부(E)를 확인하므로, 

  -- O(V^2) 의 시간 복잡도를 가진다.

- 인접 리스트를 사용하는 경우, 각 정점(V)을 방문한 후, 인접 노드를 따라 하나씩 탐색하기 때문에,

  -- O(V + E)의 시간 복잡도를 가진다.

- 그래프를 완전 탐색할 때에는 따라서, 간선이 적을 때에 인접 리스트를 사용하는 것이 좋다.

2. BFS (너비 우선 탐색)

bfs란, 루트에서 시작해서 인접한 노드를 먼저 탐색하는 방법

[출처] https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

- DFS의 경우, 깊이 있게 탐색했다면, BFS는 가까운 지점을 먼저 탐색하는 "넓은" 탐색이다.

- 참고한 블로그에서는, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때에 이 방법을 쓴다고 했다.

- BFS를 활용한 알고리즘이 바로 최단 경로를 구하는 다익스트라였다. 

  * BFS와 차이점이 있다면, 다익스트라는 DP를 사용한다는 점..

https://why-dev.tistory.com/247?category=958869 

- BFS는 구현 방법을 정리하기 보다, 문제를 보면서 얘기해보려고 한다.

- 아래는, 프로그래머스의 게임 맵 최단 거리를 구하는 문제이다.

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

(1) 코드

: 아래를 보면 알 수 있듯이, 게임 최단 거리를 구하는 문제는 BFS로 풀어야 했는데,

: 그 이유는 사방위로 움직여서 갈 수 있는 경로 중 도착지에 가까운 경로를 선택하려면,

  깊이있는 탐색보다는 너비 탐색을 통해서 사방위중 도착지에 가까운 방향 (아래로, 우측으로)으로 먼저 탐색을 하고,

  탐색한 횟수에 대해 저장하며 나아가야 했기 때문이다.

: DFS로 풀게될 경우에는 이런 탐색 횟수를 저장하며 갈 때 너무 많은 시간이 소요된다. 

  (왜냐면 깊이 탐색 후, 다시 제자리로 돌아와서 또 다른 갈래로 깊이 탐색 후, 또 다른 갈래로 깊이 탐색을 해야해서...)

: 그렇기에 그래프 최단 경로를 구할 때에도 BFS를 응용한 다익스트라를 사용한다.

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

public class Solution {

    class Node {
        int r;
        int c;
        int cnt;

        public Node(int x, int y, int cnt) {
            this.r = x;
            this.c = y;
            this.cnt = cnt;
        }
    }

    int[][] maps;
    int[][] dir = {{0, 1},{1, 0},{0, -1},{-1, 0}};

    public int solution(int[][] maps) {
        this.maps = maps;

        return bfs(maps.length, maps[0].length);
    }

    public int bfs(int r, int c){

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0, 1));
        maps[0][0] = 0;

        while (!q.isEmpty()) {
            Node cur = q.poll();

            if (cur.r == r - 1 && cur.c == c - 1) {
                return cur.cnt;
            }

            for (int[] d : dir) {
                int newR = cur.r + d[0];
                int newC = cur.c + d[1];

                if (newR >= 0 && newC >= 0 && newR < r && newC < c) {
                    if (maps[newR][newC] == 1) {
                        maps[newR][newC] = 0;
                        q.add(new Node(newR, newC, cur.cnt + 1));
                    }
                }
            }
        }

        return -1;
    }
}

[ 참고 및 출처 ]

부트캠프 수업 내용 정리

[Do it 알고리즘 코딩 테스트 - 자바 편]

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

프로그래머스 

|  HashSet<int[]>와 Hashset<ArrayList<Integer>>

문제를 풀다보면, 좌표를 집합에 넣어야 하는 경우가 있었다.

예를 들어, (0, 1), (2, 1) 

그래서 아무 생각 없이 아래와 HashSet<int[]>를 쓰게 되면 contains를 할 때 검색이 제대로 되지 않는 걸 볼 수 있다.

왜 그럴까?

이유는 배열의 경우 Hashcode를 비교하고, 

리스트의 경우 Wrapper된 Integer값을 비교하기 때문.

따라서, 좌표와 같은 수열의 집합을 만든다고 하면 HashSet 안에 ArrayList로 넣는 것이 좋다.

[ 참고 ]

https://stackoverflow.com/questions/65454683/check-if-an-array-exists-in-a-hashsetint