์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
- ์๋ฃ๊ตฌ์กฐ
- db
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- ํ๋ก๊ทธ๋๋จธ์ค
- ์์ํ์
- ๋ค์ด๋๋ฏนํ๋ก๊ทธ๋๋ฐ
- ๋ณํฉ์ ๋ ฌ
- ๋๋น์ฐ์ ํ์
- ์๊ณ ๋ฆฌ์ฆ
- ์ ๋ ฌ
- ๊ตฌํ
- Side Menu
- ๋จธ์ง์ํธ
- DFS
- ์์๊ตฌํ๊ธฐ
- ๊ทธ๋ฆฌ๋
- ๊ทธ๋ํ
- SQL
- BFS
- LIS
- ๊น์ด์ฐ์ ํ์
- ๊ทธ๋ํํ์
- DP
- ํ๋ก์ด๋์์ฌ
- ๋์ ๊ณํ๋ฒ
- ์ํ
- ์ฐ์ ์์ํ
- ๋ฐฑ์ค
- ๊ทธ๋ํ์ํ๋ฌธ์
- 11650
๋ชฉ๋ก๊ทธ๋ํ (14)
๐๐ญ๐ฐ๐ธ ๐ฃ๐ถ๐ต ๐ด๐ต๐ฆ๐ข๐ฅ๐บ
๋ฌธ์ ๋ฐฉํฅ ์๋ ๊ทธ๋ํ๊ฐ ์ฃผ์ด์ก์ ๋, ์ฐ๊ฒฐ ์์ (Connected Component)์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N๊ณผ ๊ฐ์ ์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ๊ฐ์ ์ ์ ๋์ u์ v๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ u, v ≤ N, u ≠ v) ๊ฐ์ ๊ฐ์ ์ ํ ๋ฒ๋ง ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ฐ๊ฒฐ ์์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค. ๊ทธ๋ํ ํ์ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํ์ฌ ํธ๋ ๋ฌธ์ . DFS๋ฅผ ์ฌ์ฉํ์ฌ ํ์๋ค. 0๋ฒ ์ ์ ๋ถํฐ N๊น์ง ํ๋ฒ์ฉ DFS๋ฅผ ์คํํ๋, DFS์์ ์๋ก ์ ์ ์ ๋ฐฉ๋ฌธํ ๋ ๋ง๋ค c๋ฅผ 1์ฉ ์ฆ๊ฐ์์ผ ๋ฐฉ๋ฌธํ ๋ ธ๋์ ์๋ฅผ ์ธ์ฃผ๊ณ , DFS๊ฐ ๋๋ฌ์ ๋ ๋ฐฉ๋ฌธํ ๋ ธ๋์ ์ c๊ฐ ์ด์ ๋ณด๋ค ์ฆ๊ฐํ๋ค๋ฉด ์๋ก์ด ..
๋ฌธ์ ๊ทธ๋ํ๋ฅผ DFS๋ก ํ์ํ ๊ฒฐ๊ณผ์ BFS๋ก ํ์ํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋จ, ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ ์ด ์ฌ๋ฌ ๊ฐ์ธ ๊ฒฝ์ฐ์๋ ์ ์ ๋ฒํธ๊ฐ ์์ ๊ฒ์ ๋จผ์ ๋ฐฉ๋ฌธํ๊ณ , ๋ ์ด์ ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ด ์๋ ๊ฒฝ์ฐ ์ข ๋ฃํ๋ค. ์ ์ ๋ฒํธ๋ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง์ด๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 ≤ N ≤ 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 ≤ M ≤ 10,000), ํ์์ ์์ํ ์ ์ ์ ๋ฒํธ V๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ๊ฐ์ ์ด ์ฐ๊ฒฐํ๋ ๋ ์ ์ ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ค ๋ ์ ์ ์ฌ์ด์ ์ฌ๋ฌ ๊ฐ์ ๊ฐ์ ์ด ์์ ์ ์๋ค. ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๊ฐ์ ์ ์๋ฐฉํฅ์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ DFS๋ฅผ ์ํํ ๊ฒฐ๊ณผ๋ฅผ, ๊ทธ ๋ค์ ์ค์๋ BFS๋ฅผ ์ํํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ค. V๋ถํฐ ๋ฐฉ๋ฌธ๋ ์ ์ ์์๋๋ก ์ถ๋ ฅํ๋ฉด ๋๋ค. ..
'์ฝ๋ฉ ํ ์คํธ๋ฅผ ์ํ ์๋ฃ ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ with C++' ๋ฅผ ์ฐธ๊ณ ํ์ฌ ์์ฑํ์์ต๋๋ค. ๊น์ด ์ฐ์ ํ์(DFS) ๋ณด๋ฌ๊ฐ๊ธฐ 2.2.3 ๋๋น ์ฐ์ ํ์ ; Breadth-First Search ๋๋น ์ฐ์ ํ์(BFS)์ ์์ ์ ์ ๊ณผ ๊ฐ๊น์ด ์ ์ ๋ถํฐ ๋ฐ๋ณต์ ์ผ๋ก ํ์ํด๋๊ฐ๋ ๋ฐฉ์์ ์๋ฏธํ๋ค. ๋ค์๊ณผ ๊ฐ์ ๋ชจ์์ ๊ทธ๋ํ๊ฐ ์๋ค๊ณ ๊ฐ์ ํ๋ค. 0๋ฒ์งธ ์ ์ ์ ์์์ผ๋ก ์์ ๊ฐ๋ถํฐ ์ฐพ์๊ฐ๋ค๊ณ ๊ฐ์ ํ์ ๋, BFS ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ๋ฉด ๋ค์๊ณผ ๊ฐ์ ์์๋ก ์งํ๋๋ค. 1๋จ๊ณ : 0๋ฒ ์ ์ ๋ฐฉ๋ฌธ 2๋จ๊ณ : 0๋ฒ ์ ์ ๊ณผ ์ธ์ ํ ์ ์ ์ค ๊ฐ์ฅ ๊ฐ์ด ์์ 1๋ฒ ์ ์ ๋ฐฉ๋ฌธ 3๋จ๊ณ : 0๋ฒ ์ ์ ๊ณผ ์ธ์ ํ ์ ์ ์ค ๋ฐฉ๋ฌธํ์ง ์์๊ณ , ๊ฐ์ฅ ๊ฐ์ด ์์ 2๋ฒ ์ ์ ๋ฐฉ๋ฌธ 4๋จ๊ณ : 0๋ฒ ์ ์ ๊ณผ ์ธ์ ํ ์ ์ ์ค ๋ฐฉ๋ฌธํ์ง ์์ 3๋ฒ ์ ์ ๋ฐฉ๋ฌธ 5..
'์ฝ๋ฉ ํ ์คํธ๋ฅผ ์ํ ์๋ฃ ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ with C++' ๋ฅผ ์ฐธ๊ณ ํ์ฌ ์์ฑํ์์ต๋๋ค. ๋๋ณด๊ธฐ 1. ๊ทธ๋ํ ; Graph 1.1 ๊ฐ๋ ๊ทธ๋ํ ์ํ ๋ฌธ์ ๋ฅผ ๋ค์ด๊ฐ๊ธฐ ์ ์งง๊ฒ ๊ทธ๋ํ์ ๋ํด ์ค๋ช ํ์๋ฉด, ๊ทธ๋ํ๋ ์ ์ (vertex)์ ์งํฉ๊ณผ ์ ์ ๋ค์ ์๋ก ์๋ ๊ฐ์ (edge)์ ์งํฉ์ผ๋ก ๊ตฌ์ฑ๋ ์๋ฃ๊ตฌ์กฐ๋ก ์ฐ๊ฒฐ๋์ด ์๋ ๊ฐ์ฒด ๊ฐ์ ๊ด๊ณ๋ฅผ ํํํ ์ ์๋ค. ์ํ์ ์ผ๋ก๋ G = (v๋ ์ ์ , e๋ ๊ฐ์ ์ ์งํฉ) ํํ๋ก ํํํ ์ ์๋ค. ๊ฐ์ ๋ฐฉํฅ์ ์ ๋ฌด์ ๋ฐ๋ผ ๋ฐฉํฅ ๊ทธ๋ํ(directed graph)์ ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ(undirected graph)๋ก ๋๋ ์ ์๊ณ , ๊ฐ์ ์ ๊ฐ์ค์น ์ ๋ฌด์ ๋ฐ๋ผ ๊ฐ์ค ๊ทธ๋ํ(weighted graph)์ ๋น๊ฐ์ค ๊ทธ๋ํ(unweighted graph)๋ก ๋๋๋ค. 2. ๊ทธ๋ํ ์ํ ๋ฌธ์ ..