다익스트라 알고리즘
- 다익스트라 알고리즘 이란?
다익스트라 알고리즘은 "하나의 정점에서 다른 도착지점으로 가기위한 최단거리" 를 다익스트라 알고리즘이라고 한다. 주로 우선 순위 큐로 우리는 이를 구현한다.
플로이드 와샬 알고리즘
- 플로이드 와샬 알고리즘이란?
다익스트라 알고리즘을 언급했다면 의문점을 가질 수 있다. 하나의 정점이 아닌 "모든 정점에서 다른 모든 정점으로 최단경로"를 구하고싶다면 우리는 플로이드 와샬 알고리즘을 쓴다고 한다.
다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면, 플로이드 와샬 알고리즘은 기본적으로 "거쳐가는 정점" 을 기준으로 알고리즘을 수행한다고 한다. (음..?)
영상을 보고 이해를 했다. 각 노드마다 거쳐가는 비용이 존재할때, 1 -> 2로 가는 비용이 7일때 1 -> 3 으로 가는 비용이 2, 3 -> 2 로 가는 비용이 3이라면 3을 거쳐서 가는 비용은 총 3+2로 5다. 그렇기에 3을 거쳐가는 방식이 더 저렴하다. 이런식으로 해당 노드로 갈때 다른 노드를 거쳐가는 비용이 더 저렴할 경우 그 경로로 가는 방식으로 가는 비용이 더 저렴하기에 그 노드를 거쳐가는 방식으로 갱신해준다.
다시.. 영상을 보고 확실하게 이해를 해야할거같다. 지금은 이해 했지만, 아직 설명하기엔 조금 버벅거리는거같다.
백준 11403 경로찾기
- 가중치(값)이 없는 방향 그래프가 주어진다.
- 각 정점에서 방문할 수 여부를 배열 형태로 주어진다.
- 1은 방문 가능 0은 방문 불가를 뜻한다.
import java.io.*;
import java.util.*;
public class Main {
static int[][] graph;
static int[][] answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
graph = new int[N][N];
answer = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
graph[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < N; i++) { // 거쳐가는 노드
for (int j = 0; j < N; j++) { // 출발 노드
if(graph[j][i] == 0 ){
continue;
}
answer[j][i] = 1; // 일단 답란 채워주고
for (int k = 0; k < N; k++) { // 도착 노드
if(graph[i][k] == 0 ){
continue;
}
graph[j][k] = 1;
answer[j][k] = 1;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(answer[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}
위 코드에서는 fori / forj / fork 문이 있는 3중 포문 내용이 중요하다. 처음에는 잘 이해가 안됐지만 다시 코드를 짜면서 이해가 잘된거같다.
위 코드는 비용보다는 다른 노드를 '거쳐' 갈경우 해당 노드를 갈 수 있다면 갈수없던(0) 을 갈수있도록(1) 로 변경하는 for문이다.
백준 1389 케빈 베이컨의 6단계 법칙
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static final int INF = 1000000;
static int[][] graph;
public static void main(String[] args) throws IOException {
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 int[N + 1][N + 1];
for (int i = 1; i <= N; i++) { // 모든 간선끼리 이동 값을 INF로 지정해주고
for (int j = 1; j <= N; j++) {
graph[i][j] = INF;
if (i == j) { // 자기 자신으로 이동하는건 비용이 0이니 0으로 초기화해주고
graph[i][j] = 0;
}
}
}
for (int i = 0; i < M; i++) { // 해당 입력받은 간선끼리는 값이 1이니까 1로 초기화해주고
st = new StringTokenizer(br.readLine(), " ");
int num1 = Integer.parseInt(st.nextToken());
int num2 = Integer.parseInt(st.nextToken());
graph[num1][num2] = graph[num2][num1] = 1;
}
for (int i = 1; i <= N; i++) { // 거쳐가는 노드
for (int j = 1; j <= N; j++) { // 출발 노드
for (int k = 1; k <= N; k++) { // 도착 노드
if (graph[j][k] > graph[j][i] + graph[i][k]) {
graph[j][k] = graph[j][i] + graph[i][k];
}
}
}
}
int res = INF;
int idx = -1;
for (int i = 1; i <= N; i++) {
int total = 0;
for (int j = 1; j <= N; j++) {
total += graph[i][j];
}
if(res > total) {
res = total;
idx = i;
}
}
System.out.println(idx);
}
}
위 문제가 조금 더 이해하기 쉬웠던거같다. 유튜브 영상 설명을 보면서 하다보니 경로를 갈 수 있는 비용에 따라 A에서 B로가는 경로의 값들중 가장 값싼 값으로 변경해주는 로직이 있었는데 처음 푼 문제는 갈 수 있는가? 에 따라서 1로 초기화였고
여기서는 모든 노드가 다른 노드로 갈때 가장 비용이 적게드는 노드의 값을 출력하는 부분이여서 영상을 보고 공부했던 내용과 비슷해서 상대적으로 쉬웠던거같다.
확실히 실버 2정도부터는 알고리즘이 많이나와서 한 알고리즘을 공부하면 그 알고리즘과 관련된 문제를 많이 풀어봐야할거같다. 플로이드 와샬 알고리즘.. 정말 이름 어려웠는데 이제는 기억에 잘 남는다.
