[๋ฌธ์ ํ์ด] ํ๋ก๊ทธ๋๋จธ์ค - ๊ฐ์ฅ ๋จผ ๊ฑฐ๋ฆฌ(java)
ํ๋ก๊ทธ๋๋จธ์ค - ๊ฐ์ฅ ๋จผ ๊ฑฐ๋ฆฌ(java)
https://school.programmers.co.kr/learn/courses/30/parts/14393
ํ๋ก๊ทธ๋๋จธ์ค > ๊ทธ๋ํ - ๊ฐ์ฅ ๋จผ ๊ฑฐ๋ฆฌ
๋ฌธ์ ๋ฅผ ํ๋ฉด์ ๊ณต๋ถํ ๋ด์ฉ ์ ๋๋ค !
1. ์ฒ์ ์ ์ถํ ์ฝ๋ (ํ๋ก์ด๋-์์ฌ ์๊ณ ๋ฆฌ์ฆ)
2. ๋ค์ ์ ์ถํ ์ฝ๋ (๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ)
1. ์ฒ์ ์ ์ถํ ์ฝ๋ (ํ๋ก์ด๋-์์ฌ ์๊ณ ๋ฆฌ์ฆ)
์๊ณ ๋ฆฌ์ฆ ์์ ์๊ฐ์ ๊ทธ๋ํ์ ๋ํด ๋ฐฐ์ด ์ ์ด ์๋ค.
๊ฐ์ธ์ ์ผ๋ก ๊ทธ๋ํ ๋ฌธ์ ์ค์์ ํ๋ก์ด๋-์์ฌ ์๊ณ ๋ฆฌ์ฆ์ด ๊ฐ์ฅ ๊ฐ๋จํ๋ค๊ณ ์๊ฐํด์
(๊ณต๋ถํ ๋ ๊ฐ์ฅ ์ดํด๊ฐ ์๋์ด์ ํํ..)
์ผ๋จ ์ ์ถํด๋ดค๋ค.
// ๋ฉ๋ชจ๋ฆฌ & ์๊ฐ ์ด๊ณผ
class Solution {
public int min(int a, int b) {
if (a >= b) {
return b;
} else {
return a;
}
}
public int solution(int n, int[][] edge) {
int answer = 0;
int[][] vertex = new int[n + 1][n + 1];
// ๊ทธ๋ํ ์ด๊ธฐํ
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
vertex[i][j] = 9999;
}
}
// ๊ทธ๋ํ ์์ฑ
for (int i = 0; i < edge.length; i++) {
int start = edge[i][0];
int end = edge[i][1];
vertex[start][end] = 1;
vertex[end][start] = 1;
}
// ์ต๋จ ๊ฒฝ๋ก ์
๋ฐ์ดํธ (ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ์ฆ ์ฌ์ฉ)
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
vertex[i][j] = min(vertex[i][j], vertex[i][k] + vertex[k][j]);
}
}
}
int max = 0;
// 1๋ฒ ๋
ธ๋์์ ๊ฐ์ฅ ๋จผ ๊ฑฐ๋ฆฌ ๊ตฌํ๊ธฐ
for (int i = 2; i <= n; i++) {
if (max < vertex[1][i]) {
max = vertex[1][i];
}
}
// ๊ฐ์ฅ ๋จผ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ์ง ๊ฐ์ ๋
ธ๋์ ๊ฐ์ ๊ตฌํ๊ธฐ
for (int i = 2; i <= n; i++) {
if (vertex[1][i] == max) {
answer++;
}
}
return answer;
}
}
ํ ์คํธ 6๊น์ง๋ ํต๊ณผํ์ง๋ง, ํ๋ก์ด๋-์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๊ฐ O(N^3)์ด๊ธฐ ๋๋ฌธ์
ํ ์คํธ 7๋ถํฐ ๋ฉ๋ชจ๋ฆฌ์ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค.
- ํ๋ก์ด๋-์์ฌ ์๊ณ ๋ฆฌ์ฆ
์ฒ์์ ๋ชจ๋ ๊ฑฐ๋ฆฌ๋ฅผ ๋ชจ๋ฅธ๋ค๊ณ ๊ฐ์ ํ์ฌ 9999๋ก ์ด๊ธฐํํ๊ณ , ๋ค์์ผ๋ก ๊ฐ์ ์ด ์กด์ฌํ๋ฉด 1๋ก ์ด๊ธฐํ ํ๋ค.
[0][n], [n][0]์ ์ฌ์ฉํ์ง ์์ ๊ฒ์ด๊ธฐ ๋๋ฌธ์ ๋ชจ๋ ๋ฐ๋ชฉ๋ฌธ์ 1๋ก ์์ํ๋๋ก ํ๋ค.
์ฐ๋ฆฌ๋ 1->2๋ก ๊ฐ ๋๋ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ 1์์ ์๊ณ ์์ง๋ง, 1->4๋ก ๊ฐ ๋๋ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ ์๋ค.
๊ทธ๋ ๋ค๋ฉด ์ด๋ป๊ฒ ์ ์ ์๋๊ฑธ๊น?
๋ฐ๋ก 1->2, 2->4์ ๊ฐ์ด ์ฐ๊ฒฐ๋๋ ์ง์ ์ ํตํ์ฌ 1->4๋ก ์ด๋ํ ์ ์๋ค๋ ์ฌ์ค์ ํ์ฉํ๋ฉด ๋๋ค.
์ด ์ ์ ์ด์ฉํ์ฌ vertex[i][k] + vertex[k][j]์ ๊ฐ์ด ์ฝ๋๋ฅผ ์์ฑํ ์ ์๊ณ ,
์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ ๋ฐ์ดํธ ํด์ผํ๊ธฐ ๋๋ฌธ์ vertex[i][j] = min(vertex[i][j], vertex[i][k] + vertex[k][j]); ๊ฐ ๋๋ค.
๊ทธ๋์ ์ต์ข ์ ์ผ๋ก ์์ ๊ฐ์ด ์ฝ๋๋ฅผ ์์ฑํ ์ ์๋ค.
2. ๋ค์ ์ ์ถํ ์ฝ๋ (๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ)
๋ฉ๋ชจ๋ฆฌ์ ์๊ฐ์ ์ ๊ฒฝ ์จ์ ์ฝ๋๋ฅผ ์์ฑํ๋ ค๋ฉด ๋ ํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ด ํ์ํ๋ค.
๋ค์ต์คํธ๋ผ, ํ๋ฆผ, ๋ฒจ๋ง-ํฌ๋, ํฌ๋ฃจ์ค์นผ, DFS, BFS ๋ฑ.. ๋ค์ํ ์๊ณ ๋ฆฌ์ฆ์ด ์กด์ฌํ๋ค.
๊ฐ๊ฐ ์๊ณ ๋ฆฌ์ฆ๋ง๋ค ์ฌ์ฉํ๋ ๋ชฉ์ ์ด ์์ด์ ์ฝ๋๋ฅผ ์์ฑํ๋ ค๊ณ ํ์ง๋ง
๊ฐ๋ ์ด ๊ฐ๋ฌผ๊ฐ๋ฌผํด์ ๋ค์ ์ฐพ์๋ดค๋ค.
์ด ๋ฌธ์ ๋ ์ฃผ์ด์ง ์ ์ ์์ ๋ชจ๋ ๋ค๋ฅธ ๊ฒฝ๋ก์ ์ ์ ๊น์ง ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๊ฒ์ด๊ธฐ์
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๊ตฌํํด์ผํ๋ ๋ฌธ์ ์๋ค.
์์ผ๋ก ๊ฐ ์๊ณ ๋ฆฌ์ฆ์ ํน์ฑ๊ณผ ๊ฐ๋ ์ ํ์คํ๊ฒ ํ๊ณ ,
๋ฌธ์ ๋ฅผ ์ ์ฝ๊ณ ํ์ด์ผ๊ฒ ๋ค. (ใฑ-)
import java.util.*;
class Solution {
public int solution(int n, int[][] edge) {
final int INF = 9999;
// ๊ทธ๋ํ ์ด๊ธฐํ
List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
// ๊ทธ๋ํ ์์ฑ
for (int[] e : edge) {
int start = e[0];
int end = e[1];
graph.get(start).add(new int[]{end, 1});
graph.get(end).add(new int[]{start, 1});
}
// ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ
int[] distances = new int[n + 1];
Arrays.fill(distances, INF);
distances[1] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
pq.offer(new int[]{1, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int node = current[0];
int distance = current[1];
if (distance > distances[node]) continue;
for (int[] neighbor : graph.get(node)) {
int nextNode = neighbor[0];
int weight = neighbor[1];
int nextDistance = distance + weight;
if (nextDistance < distances[nextNode]) {
distances[nextNode] = nextDistance;
pq.offer(new int[]{nextNode, nextDistance});
}
}
}
// ์ต๋ ๊ฑฐ๋ฆฌ ์ฐพ๊ธฐ
int maxDistance = 0;
for (int i = 1; i <= n; i++) {
if (distances[i] != INF && distances[i] > maxDistance) {
maxDistance = distances[i];
}
}
// ์ต๋ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ์ง ๋
ธ๋์ ๊ฐ์ ์ธ๊ธฐ
int answer = 0;
for (int i = 1; i <= n; i++) {
if (distances[i] == maxDistance) {
answer++;
}
}
return answer;
}
}
- ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋ ์ค ๊ฐ์ฅ ์ ์ ๋น์ฉ์ ๊ฐ์ง๋ ๋ ธ๋๋ฅผ ์ ํํ๊ณ
ํด๋น ๋ ธ๋๋ก๋ถํฐ ๊ฐ ์ ์๋ ๋ ธ๋๋ค์ ๋น์ฉ์ ๊ฐฑ์ ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์ด๋ ์ฐ์ ์์ ํ์ ์์ฐจ ํ์์ผ๋ก ์ฝ๋๋ฅผ ์์ฑํ ์ ์๋ค.
์์ฐจ ํ์์ ์๊ฐ ๋ณต์ก๋๋ O(N^2)์ด๊ณ , ์์์ O(N^3)์ผ ๋ ์ค๋ฅ๊ฐ ์๊ฒผ๊ธฐ ๋๋ฌธ์
์๊ฐ ๋ณต์ก๋๊ฐ O(E log V)์ธ ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๊ณ ์ ํ์๋ค.
1๋ฒ ๋ ธ๋์์ 6๋ฒ ๋ ธ๋๊น์ง ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ๋ distances ๋ฐฐ์ด๊ณผ
๋ ธ๋ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ์ฒดํฌํ๋ pq ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํด์ ์๊ณ ๋ฆฌ์ฆ์ ์์ฑํ๋ค.
int[] current = pq.poll(); ์ฝ๋๋ฅผ ํตํด ์ฐ์ ์์ ํ์์ ์ ์ ๊ณผ ๊ฑฐ๋ฆฌ๋ฅผ current ๋ฐฐ์ด์ ์ ์ฅํ๋ค.
for๋ฌธ์ ํตํด ๋ค์ ๋ ธ๋๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์ ํ๋ค.
์ด๋ฒ์๋ ๋ค์ต์คํธ๋ผ ๋ฌธ์ ๋ฅผ ํ์ด๋ดค์ต๋๋ค.
๋ค์ ํฌ์คํ ์์ ๋ง๋๋ด ์๋ค์ !