백준

https://www.acmicpc.net/problem/1753 해당 백준 문제는 다익스트라 알고리즘을 사용한, 최단 경로를 구하는 문제이다.우선, 다익스트라 알고리즘에 대해 설명해보도록 하겠다. 1. 다익스트라 알고리즘이란?https://www.youtube.com/watch?v=pVfj6mxhdMw 첨부한 유튜브 영상을 통해 쉽게 이해할 수 있지만다익스트라(Dijkstra) 알고리즘은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다.이 알고리즘은 비음수 가중치를 가진 그래프에서만 사용할 수 있다. - 방향 그래프 또는 무방향 그래프- 각 간선에 대한 비음수 가중치- 시작 정점 위 세가지가 주어지면, 시작 정점에서 모든 정점까지의 최단 거리를 구하면 된다.여기서 간선 가중치..

https://www.acmicpc.net/problem/2206 입력첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.출력첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다. 해당 백준 문제는 BFS를 심화한 문제로, NxM의 숫자 맵에 1이 존재할 경우(벽이 존재할 경우), 이 벽을 허물 수 있다는 경우의 수까지 포함하여 최단 거리를 구하는 문제이다. 단, 벽은 한번만 허물 수 있다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.  우선, 기존의 BFS 최단거리 문제 틀에서 ..

https://www.acmicpc.net/problem/1707  해당 백준 문제는 이분 그래프 판별 문제이다.BFS, DFS 문제를 꾸준히 풀었다면 쉽게 풀이할 수 있을 것이다. 이분 그래프란?: 그래프의 정점들을 두 개의 집합으로 나누었을 때, 각 집합에 속한 정점끼리는 서로 간선으로 연결되지 않으며두 집합에 속한 정점들끼리만 간선으로 연결된다는 것. (1) 정점 집합 분할 : 이분 그래프는 정점들을 두 개의 집합으로 나눌 수 있다.즉, 집합 A와 집합 B가 있고, 각 간선은 집합 A의 정점과 집합 B의 정점 간에만 존재한다. (2) 인접 정점  : 두 집합에 속한 정점들은 서로 인접해야 하며, 같은 집합에 속한 정점들끼리는 인접하지 않다.   이분 그래프인지 아닌지를 탐색하는 데에는 BFS, DF..

https://www.acmicpc.net/problem/1012   해당 문제는 배추를 보호하기 위한 배추흰지렁이의 수를 구하기 위해, 그래프 순회 알고리즘을 사용하는 문제이다.이전 단계에서 DFS, BFS 문제를 풀이했었다면, 이 문제도 큰 어려움 없이 문제를 풀 수 있다. import java.util.*;public class Main { // 방향 벡터 (상, 하, 좌, 우) static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t =..