๐ ํ๋ก๊ทธ๋๋จธ์ค / Graph / Level 3 / ์์
๐ ๋ฌธ์
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๐ซ ์ ํ ์ฌํญ
- ์ ์์ ์๋ 1๋ช ์ด์ 100๋ช ์ดํ์ ๋๋ค.
- ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ๋ 1๊ฐ ์ด์ 4,500๊ฐ ์ดํ์ ๋๋ค.
- results ๋ฐฐ์ด ๊ฐ ํ [A, B]๋ A ์ ์๊ฐ B ์ ์๋ฅผ ์ด๊ฒผ๋ค๋ ์๋ฏธ์ ๋๋ค.
- ๋ชจ๋ ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ์๋ ๋ชจ์์ด ์์ต๋๋ค.
๐ ์ ์ถ๋ ฅ ์
| n | results | return |
| 5 | [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] | 2 |
๐ค ํ์ด ๋ฐฉ๋ฒ
1๏ธโฃ ๋ด ์๊ฐ ์ ๋ฆฌ
โก๏ธ ์๋ 2๊ฐ์ง ๋ฐฉ๋ฒ์ ์๊ฐํด๋ณด์์ง๋ง ์ฝ๋๋ก ์ฎ๊ธฐ๊ฑฐ๋ ๋ ผ๋ฆฌ์ ๊ตฌ์์ด ์ด๋ ค์ ๋ค. ๋ฐ๋ผ์ ๋ค๋ฅธ ๋ธ๋ก๊ทธ ๊ธ์ ์ฐธ๊ณ ํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์๋ค.
โ ๋ฐฐ์ด์ ํ์ฉ
โก๏ธ ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ์ ๋ฐ๋ผ ์ ์๋ค์ ๋ฐฐ์ด ์ธ๋ฑ์ค๋ฅผ ๋ฐ๊ฟ๋๊ฐ๋ฉด์ ์์๋ฅผ ํ์ธํ๊ณ ์ ํ๋ค. ๊ทธ๋ฌ๋ ์ด ๋ฐฉ๋ฒ์ ์ฝ๋๋ก ๊ตฌํ์ด ๋ถ๊ฐ๋ฅ ํ๋ค.
โก depth ๋ฅผ ํ์ฉ
โก๏ธ ๋ฐฉํฅ ๊ทธ๋ํ๋ฅผ ์์ฑํ์ฌ ๊ฐ์ฅ ๊น์ depth ๋ฅผ ๊ตฌํด ํ์ฉํด๋ณด๊ณ ์ ํ๋ค. ๊ทธ๋ฌ๋ ์ด ๋ฐฉ๋ฒ์ ์ ๊ทผ ๋ฐฉ์ ์์ ๊ฐ ์๋ชป๋์๋ค.
2๏ธโฃ Floyd-Warshall ์๊ณ ๋ฆฌ์ฆ
โก๏ธ ํ๋ก์ด๋-์์ (Floyd-Warshall) ์๊ณ ๋ฆฌ์ฆ์ด ์ด ๋ฌธ์ ๋ฅผ ํธ๋ ๋ํ์ ์ธ ๋ฐฉ๋ฒ์ด๋ผ๊ณ ๋์์์๋ค.
โ Floyd-Warshall Algorithm ์ด๋?
โก๏ธ ๋ฐฉํฅ์ฑ ๊ฐ์ค์น ๊ทธ๋ํ์์ "์ต๋จ๊ฑฐ๋ฆฌ"๋ฅผ ์ฐพ๋ ๊ฒ์ ๋ชฉ์ ์ผ๋ก ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ํ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก๋ "๋ค์ต์คํธ๋ผ" ๋ ์๋๋ฐ, ๋ค์ต์คํธ๋ผ์ ๊ฒฝ์ฐ ํ ์ ์ ์ผ๋ก๋ถํฐ์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ์ง๋ง ํ๋ก์ด๋-์์ ์๊ณ ๋ฆฌ์ฆ์ ๊ฒฝ์ฐ ๋ชจ๋ ์ ์ ์ผ๋ก๋ถํฐ์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ค๋ ์ ์์ ์ฐจ์ด๊ฐ ์๋ค๊ณ ํ๋ค.
โก Floyd-Warshall Algorithm ์ ๋ ผ๋ฆฌ

โก๏ธ ์ ๊ทธ๋ฆผ์์ ์ ์ A ์์ ์ ์ C ๋ก ๊ฐ๋ ๋ฐฉ๋ฒ์ โ G[A, C] = 8 ๊ณผ โก G[A,B] + G[B,C] = 2+3 = 5 ๊ฐ ์๋ค. ๋ ๋ฐฉ๋ฒ ๋ชจ๋ C ๋ก ๊ฐ ์ ์์ง๋ง, ๊ฐ์ B๋ฅผ ๊ฑฐ์ณ์ ๊ฐ๋ ๋ฐฉ๋ฒ์ด ๋ ํจ์จ์ ์ด๊ธฐ ๋๋ฌธ์ ๋ ์์ ๊ฐ์ธ 5๋ฅผ ์ ์ฅํ๊ฒ ๋๋ค.
โข Floyd-Warshall Algorithm ๊ตฌํ
// Pseudo Code
let dist be a
procedure FloydWarshallWithPathReconstruction() is
// ์ด๊ธฐํ
for each edge (u, v) do
dist[u][v] ← w(u, v) // The weight of the edge (u, v)
prev[u][v] ← u
for each vertex v do
dist[v][v] ← 0
prev[v][v] ← v
// ๋ณธ๊ฒฉ์ ์ธ Floyd-Washall ์ํ
for k from 1 to |V| do
for i from 1 to |V|
for j from 1 to |V| // ์ค๊ฐ๊ฐ๋ค์ ๊ณ์ ํ์ธํ๋ฉด์ min ๊ฐ์ผ๋ก ๋์ฒด
if dist[i][j] > dist[i][k] + dist[k][j] then
dist[i][j] ← dist[i][k] + dist[k][j]
prev[i][j] ← prev[k][j]
3๏ธโฃ ํ์ด์ ์ฉ (Floyd-Warshall Algorithm)
โก๏ธ ํด๋น๋ฌธ์ ๋ ๊ฐ์ค์น ๊ทธ๋ํ์ ํํ๋ ์๋๊ธฐ ๋๋ฌธ์ ์์ ํ ํ๋ก์ด๋-์์ ์๊ณ ๋ฆฌ์ฆ์ ๋ถํฉํ๋ค๊ณ ํ ์๋ ์๋ค. ํ์ง๋ง ํด๋น ๋ฌธ์ ์ ์์ ์ ๊ฒฝ๊ธฐ๊ฒฐ๊ณผ๋ฅผ ์ ์ ์๋ ๊ฒ๋ค์ ๊ฒฐ๊ณผ๊ฐ ์๋ ค์ง ๊ฒฝ๊ธฐ๋ค์ ํตํด์ ์ ์ ์๋๋์ด๋ค.
์์) [1, 4], [4, 5]
์ ํ ์ํฉ) ์ค๋ ฅ ์ฐจ์ด๋ ์ ๋์ ์ด๋ค.
โก๏ธ 1๋ฒ ์ ์๊ฐ 4๋ฒ ์ ์๋ฅผ ์ด๊ฒผ๊ณ , 4๋ฒ ์ ์๋ 5๋ฒ ์ ์๋ฅผ ์ด๊ธด ์ํฉ์ด๋ค.
โก๏ธ 1๋ฒ & 5๋ฒ ์ ์์ ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ๋ ์๋ ค์ง์ง ์์์ง๋ง ์ ์ํฉ์ ๋ฐํ์ผ๋ก 1๋ฒ ์ ์๊ฐ 5๋ฒ ์ ์๋ฅผ ์ด๊ฒผ์ ๊ฑฐ๋ผ๋ ์ถ๋ก ์ด ๊ฐ๋ฅํ๋ค.
โก๏ธ ๋ฐ๋ผ์ ์ด ๋ฌธ์ ๋ ํ๋ก์ด๋-์์ ์ ์ผ๋ฐ์ ์ธ ์ฝ๋์์ min ๊ฐ์ ๋น๊ตํ๋ ๊ฒ์ด ์๋, ์ค๊ฐ๊ฐ ๊ฒฐ๊ณผ๊ฐ ์กด์ฌํ๋์ง๋ฅผ ํ์ธํ๋ ๊ฒ์ผ๋ก ๋ณํ์ ํด์ฃผ๋ฉด ๋๋ค.
// ํ๋ก์ด๋-์์
๋ณํ
for (int k=0; k<n; k++) {
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (i == j) continue;
if (result[i][k] == 1 && result[k][j] == 1) {
result[i][j] = 1;
}
}
}
}
4๏ธโฃ ๊ฒฐ๊ณผ ํ์ธ
โก๏ธ ๋ชจ๋ ํ ์คํธ ์ฝ๋์์ ์ ๋์๊ฐ๋ค.

๐ป ํ์ด ์ฝ๋
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
// ๊ฒฐ๊ณผ๋ฅผ ๋ด๊ธฐ ์ํ ์ธ์ ํ๋ ฌ
int[][] result = new int[n][n];
// results ๋ฐฐ์ด๊ฐ ๋ด๊ธฐ
for (int[] r : results) {
result[r[0]-1][r[1]-1] = 1;
}
// Floyd-Warshall Algorithm ์ ์ฉ (๋ณํ ver)
// ์ค๊ฐ ๋
ธ๋๋ฅผ ๋ฐ๋ณต๋ฌธ์ ์ฒ์์ ๋ฐฐ์น
for (int k=0; k<n; k++) {
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (i == j) continue;
if (result[i][k] == 1 && result[k][j] == 1) {
result[i][j] = 1;
}
}
}
}
int cnt = 0;
// ์์ ํ์ ์ ์ ์ ๋์ถ
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (i==j) continue;
if (result[i][j] == 1 || result[j][i] == 1) cnt++;
}
// ๊ฒฐ๊ณผ๋ฅผ ์๋ ๊ฒฝ๊ธฐ ์๊ฐ ์ ์ฒด ์ ์์ ์-1 ๊ณผ ๊ฐ์ผ๋ฉด ์์ ํ์
// ex) ์ ์๊ฐ 5๋ช
์ธ ๊ฒฝ์ฐ ํ ์ ์์ ๋ํด 4๊ฒฝ๊ธฐ์ ๋ํ ๊ฒฐ๊ณผ๋ฅผ ๋ชจ๋ ์์์ผ ์์ ํ์
if (cnt == n-1) answer++;
cnt=0;
}
return answer;
}
}
๐ค ๊ถ๊ธํ ์
โก๏ธ ๋งจ์ฒ์ Floyd-Warshall ์ ๊ณต๋ถํ๊ณ ์ ์ฉ์์ผ๋ณด์์ ๋ ๋ฐ๋ณต๋ฌธ์ ๋๋ ์์ ๋๋ฌธ์ ํ ์คํธ ์ผ์ด์ค์ ํต๊ณผํ์ง ๋ชปํ๋ ๊ฒฝ์ฐ๋ค์ด ์์๋ค. ์ฝ๋๋ฅผ ํ์ธํด๋ณด๋ ๋๋ ์์๊ฐ ์ค๊ฐ ๋ ธ๋ > ์์ ๋ ธ๋ > ๋์ฐฉ ๋ ธ๋ ์๋ค. ์ฐพ์๋ณด๋ ๊ฑฐ์ณ๊ฐ๋ ๋ ธ๋๋ฅผ ํ๋์ฉ ํ์ธํ๋ ๊ฒ์ด๋ฏ๋ก ์ค๊ฐ ๋ ธ๋๋ฅผ ๋งจ ์์ ๋๋ ๊ฒ ๊ฐ์๋๋ฐ ์์งํ ์์ง ๋ ผ๋ฆฌ์ ์ผ๋ก ํด๋น ์์๊ฐ ์ง์ผ์ ธ์ผํ๋์ง๋ ์ดํดํ์ง ๋ชปํ๋ค.