728x90 Graph7 [graph] ๋๋น ์ฐ์ ํ์(BFS, Breadth First Search) ๋๋น ์ฐ์ ํ์(BFS, Breadth First Search) ์์ ์ ์ ์ผ๋ก๋ถํฐ ์ธ์ ํ ์ ์ ๋ค์ ๋ชจ๋ ์ฐจ๋ก๋ก ๋ฐฉ๋ฌธํ ํ ๋ฐฉ๋ฌธํ๋ ์ ์ ์ ๋ค์ ์์์ ์ผ๋ก ํ์ฌ ์ธ์ ํ ์ ์ ๋ค์ ์ฐจ๋ก๋ก ๋ฐฉ๋ฌธํ๋ ๋ฐฉ๋ฒ ๊ฐ๊น์ด ์ ์ ๋ค์ ๋จผ์ ๋ฐฉ๋ฌธํ๊ณ ๋ฉ๋ฆฌ ์๋ ์ ์ ๋ค์ ๋์ค์ ๋ฐฉ๋ฌธํ๋ ์ํ ๋ฐฉ๋ฒ ์ธ์ ํ ์ ์ ๋ค์ ๋ํด ์ฐจ๋ก๋ก ๋ค์ ๋๋น ์ฐ์ ํ์์ ๋ฐ๋ณตํด์ผ ํ๋ฏ๋ก ์ ์ ์ ์ถ(First-IN First-Out) ๊ตฌ์กฐ์ธ ํ(Queue) ์ฌ์ฉ BFS ์ํ์์ ํ๊ฐ ๊ณต๋ฐฑ์ด ๋ ๋๊น์ง ๋นจ๊ฐ ์์ ๋ถ๋ถ์ ๋ฐ๋ณตํ๋ค. BFS ๊ณผ์ ํํ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ Queue๊ฐ ๋น์์ผ๋ฏ๋ก ํ์ ์ข ๋ฃ ๊ฒฐ๊ณผ : 1 → 2 → 4 → 3 → 5 ์ธ์ ํ๋ ฌ๋ก ๊ตฌํํ ๊ทธ๋ํ BFS static void BFS(int[][] graph, int v) { /.. 2023. 3. 7. [graph] ๊น์ด ์ฐ์ ํ์(DFS, Depth First Search) ๊ทธ๋ํ ์ํ(Graph Traversal) ๋๋ ๊ทธ๋ํ ํ์(Graph Search) ๋? ํ๋์ ์ ์ ์์ ์์ํ์ฌ ๊ทธ๋ํ์ ์๋ ๋ชจ๋ ์ ์ ์ ํ๋ฒ์ฉ ๋ฐฉ๋ฌธํ๋ ๊ฒ ๊น์ด ์ฐ์ ํ์(DFS, Depth First Search) ์์ ์ ์ ์์ ํ ๋ฐฉํฅ์ผ๋ก ๊ฐ ์ ์๋ ๊ฐ์ฅ ๋จผ ๊ฒฝ๋ก๊น์ง ๊น์ด ํ์ํด๊ฐ๋ค๊ฐ ๋ ์ด์ ๊ฐ ๊ณณ์ด ์์ผ๋ฉด ๊ฐ์ฅ ๋ง์ง๋ง์ ๋ง๋ฌ๋ ๊ฐ์ ์ด ์๋ ์ ์ ์ผ๋ก ๋๋์์์ ๋ค๋ฅธ ๋ฐฉํฅ์ ๊ฐ์ ์ผ๋ก ํ์์ ๊ณ์ํจ์ผ๋ก์จ ๋ชจ๋ ์ ์ ์ ๋ฐฉ๋ฌธํ๋ ์ํ๋ฐฉ๋ฒ ๋ง์ง๋ง ๊ฐ๋ฆผ๊ธธ๋ก ๋๋์๊ฐ์ผํ๋ฏ๋ก ํ์ ์ ์ถ(Last-IN-First-Out) ๊ตฌ์กฐ์ธ ์คํ(Stack) ์ฌ์ฉ ์ฌ์ค์ ๋ฐฑํธ๋ํน๊ณผ ๋๊ฐ์ ๊ฐ๋ ์ ์ฌ์ฉํ๋ค. DFS ์ํ ์์ ์คํ์ด ๊ณต๋ฐฑ์ด ๋ ๋๊น์ง ๋นจ๊ฐ ์์ ๋ถ๋ถ์ ๋ฐ๋ณตํ๋ค. DFS ๊ณผ์ ํํ ↓ ↓ ↓ ↓ ↓ ↓ ↓ .. 2023. 3. 6. [graph] ์ธ์ ๋ฆฌ์คํธ๋ก ๋ฐฉํฅ ๊ทธ๋ํ ๊ตฌํํ๊ธฐ โ ์ ์ ์ ๊ฐ์ n๊ฐ , ๋ชจ์๋ฆฌ์ ๊ฐ์ m๊ฐ โ ์์ ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ ๊ตฌํํ ๊ฒ์๊ธ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ฆฌ์คํธ์ ๊ฐ ๋ ธ๋๋ ์ ์ ์ ์ ์ฅํ๋ ํ๋์ ๋ค์ ์ธ์ ์ ์ ์ ์ฐ๊ฒฐํ๋ ๋งํฌ ํ๋๋ก ๊ตฌ์ฑ๋๋ค. ์ ์ i์ ์ง์ถ ์ฐจ์ = i์ ๋ ธ๋์ ์ ex) ์ ์ 2์ ์ง์ถ ์ฐจ์ = 2 JAVA ์๋ฃ๊ตฌ์กฐ ๊ตฌํ ์ฝ๋ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; class Node { int vertex; //์ ์ Node link; //๋ค์ ์ฐ๊ฒฐ๋์ด ์๋.. 2023. 3. 4. [graph] ์ธ์ ๋ฆฌ์คํธ๋ก ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ ๊ตฌํํ๊ธฐ โ ์ ์ ์ ๊ฐ์ n๊ฐ , ๋ชจ์๋ฆฌ์ ๊ฐ์ m๊ฐ โ ๊ฐ ์ ์ ์ ๋ํ ์ธ์ ์ ์ ๋ค์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก ๋ง๋๋ ๊ฒ ๋ฆฌ์คํธ์ ๊ฐ ๋ ธ๋๋ ์ ์ ์ ์ ์ฅํ๋ ํ๋์ ๋ค์ ์ธ์ ์ ์ ์ ์ฐ๊ฒฐํ๋ ๋งํฌ ํ๋๋ก ๊ตฌ์ฑ๋๋ค. ์ด๋ค ์ ์ ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ๊ทธ ์ ์ ์ ์ธ์ ํ ์ ์ ์ ์(= ์ ์ ์ ์ฐจ์)๋งํผ ๋ ธ๋๊ฐ ์ฐ๊ฒฐ๋์ด ์๋ค. ์ ์ i์ ์ฐจ์ = i์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋ ์ ex) ์ ์ 2์ ์ฐจ์ = 3 JAVA ์๋ฃ๊ตฌ์กฐ ๊ตฌํ ์ฝ๋ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTo.. 2023. 3. 4. [graph] ์ธ์ ๋ฐฐ์ด๋ก ๋ฐฉํฅ ๊ทธ๋ํ ๊ตฌํํ๊ธฐ โ ์ ์ ์ ๊ฐ์ n๊ฐ , ๋ชจ์๋ฆฌ์ ๊ฐ์ m๊ฐ โ ์์ ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ๋ฅผ ๊ตฌํํ ๊ฒ์๊ธ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก n X n ์ด์ฐจ์ ๋ฐฐ์ด(์ ์ ์ ์์ ๋ํ ์ ๋ฐฉํ๋ ฌ)์ ์ฌ์ฉํ์ฌ ๋ ์ ์ ์ฌ์ด์ ๊ฐ์ ์ด ์กด์ฌํ๋ฉด 1, ์กด์ฌํ์ง ์์ผ๋ฉด 0์ผ๋ก ์ ์ฅํ๋ค. ํ๋ ฌ์ ๋๊ฐ์ ๊ฐ์ ํญ์ 0์ด๋ค. ๊ทธ๋ฌ๋ ≠ ์ด๋ฏ๋ก ๋์นญ์ ์ด๋ฃจ์ง๋ ์๋๋ค. ํ i์ ํฉ = ์ ์ i์ ์ง์ถ ์ฐจ์ ์ด i์ ํฉ = ์ ์ i์ ์ง์ ์ฐจ์ ex) ์ ์ 2์ ์ง์ถ ์ฐจ์ = 0 + 0 + 1 + 1 = 2 ์ ์ 2์ ์ง์ ์ฐจ์ = 1 + 0 + 0 + 0 = 1 JAVA ๊ตฌํ ์ฝ๋ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java... 2023. 3. 4. [graph] ์ธ์ ๋ฐฐ์ด๋ก ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ ๊ตฌํํ๊ธฐ โ ์ ์ ์ ๊ฐ์ n๊ฐ , ๋ชจ์๋ฆฌ์ ๊ฐ์ m๊ฐ โ ๊ทธ๋ํ๋ฅผ ๊ตฌ์ฑํ๋ ์ ์ ์ ๋ํด์ ๋ ์ ์ ์ ์ฐ๊ฒฐํ๋ ๊ฐ์ ์ ์ ๋ฌด๋ฅผ ์ ์ฅํ๋ ๋ฐฉ๋ฒ n X n ์ด์ฐจ์ ๋ฐฐ์ด(์ ์ ์ ์์ ๋ํ ์ ๋ฐฉํ๋ ฌ)์ ์ฌ์ฉํ์ฌ ๋ ์ ์ ์ฌ์ด์ ๊ฐ์ ์ด ์กด์ฌํ๋ฉด 1, ์กด์ฌํ์ง ์์ผ๋ฉด 0์ผ๋ก ์ ์ฅํ๋ค. ์ด๋, ํ๋์ ์ ์ ์์ ์๊ธฐ ์์ ์ผ๋ก ๊ฐ์ (=์์ฒด ๊ฐ์ )์ ์กด์ฌํ ์ ์์ผ๋ฏ๋ก ํ๋ ฌ์ ๋๊ฐ์ ๊ฐ์ ํญ์ 0 ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ์ ๊ฒฝ์ฐ ํ๋ ฌ์ (i, j)์ (j,i)์ ๊ฐ์ด ๊ฐ์ผ๋ฏ๋ก ๋๊ฐ์ ์ ์ค์ฌ์ผ๋ก ๋์นญ์ ์ด๋ฃฌ๋ค. ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ์์ ํ i์ ํฉ = ์ด i์ ํฉ = ์ ์ i์ ์ฐจ์ ex) ์ ์ 2์ ์ฐจ์ = 2ํ์ ํฉ(=1+0+1+1) = 2์ด์ ํฉ(=1+0+1+1) = 3 JAVA๋ก ๊ตฌํํ ์ฝ๋ import java.io.BufferedReader;.. 2023. 3. 4. [graph] ๊ธฐ๋ณธ ๊ฐ๋ ์ ๋ฆฌ 1. ๊ทธ๋ํ G = (V, E) V(vertex) ์ ์ : ์ฐ๊ฒฐํ ๊ฐ์ฒด๋ฅผ ๋ํ๋ด๋ ๊ฒ E(edge) ๋ชจ์๋ฆฌ : ํ์์ ์ ์ ์ ์ด์ ๊ฒ graph๋? ์ฐ๊ฒฐ๋์ด์๋ ์์๊ฐ์ ๊ด๊ณ๋ฅผ ํํํ ์๋ฃ๊ตฌ์กฐ ์ฆ, ์ ์ ๊ณผ ๊ฐ์ ์ ์งํฉ 2. ๊ทธ๋ํ์ ์ข ๋ฅ ์ข ๋ฅ ์ค๋ช ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ(undirected graph) ๊ฐ์ ์ ๋ฐฉํฅ์ด ์๋ ๊ทธ๋ํ ์์์ ๋ชจ์๋ฆฌ (x, y)∈E ์ด๋ฉด (y, x)∈E ๋ฅผ ๋ง์กฑํ๋ค. ์ฆ, (x, y)์ (y, x)๋ ๊ฐ์ ๊ฐ์ ์ ๋ํ๋ธ๋ค. ๋ฐฉํฅ ๊ทธ๋ํ(directed graph) = ๋ค์ด๊ทธ๋ํ(digraph) ๊ฐ์ ์ ๋ฐฉํฅ์ด ์๋ ๊ทธ๋ํ = i → j = ๋ก ํํ ์์์ ๋ชจ์๋ฆฌ (x, y)∈E ์ด๋ฉด (y, x)∈E ๋ฅผ ๋ง์กฑํ์ง ์๋๋ค. ์์ ๊ทธ๋ํ(complete graph) ํ ์ ์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ .. 2023. 3. 3. ์ด์ 1 ๋ค์ 728x90