์ ์ฒด ๊ธ
-
[๋ฐฑ์ค(BOJ) 11729๋ฒ] ํ๋ ธ์ด ํ ์ด๋ ์์ (C++)PS(Problem Solving)/C++ 2022. 1. 31. 14:42
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/11729 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์ฒซ ๋ฒ์งธ ์ฅ๋์ ์์ธ ์ํ์ ๊ฐ์ N (1 ≤ N ≤ 20)์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ๋ ๋ฒ์งธ ์ค๋ถํฐ ์ํ ๊ณผ์ ์ ์ถ๋ ฅํ๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ K๊ฐ์ ์ค์ ๊ฑธ์ณ ๋ ์ ์ A B๋ฅผ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ถ๋ ฅํ๋๋ฐ, ์ด๋ A๋ฒ์งธ ํ์ ๊ฐ์ฅ ์์ ์๋ ์ํ์ B๋ฒ์งธ ํ์ ๊ฐ์ฅ ์๋ก ์ฎ๊ธด๋ค๋ ๋ป์ด๋ค. ํ์ด ์ฌ๊ท๋ฅผ ์ด์ฉํด์ ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ์ฌ๊ท๋ฅผ ๊ณต๋ถํ ๋ ๊ท๋ฉ์ ์ฌ๊ณ ๋ฅผ ํตํด์ ํด๊ฒฐํ๋ผ๋ ๋ง์ด ์๋ค. n-1๊ฐ์ ์ํ์ 2๋ฒ ์ผ๋ก ๋ชจ๋ ์ฎ๊ธด ํ, n๋ฒ ์ํ์ 3๋ฒ์ผ๋ก ์ฎ๊ธฐ๊ณ , 2๋ฒ์ผ๋ก ์ฎ๊ฒผ๋ n-1๊ฐ์ ์ํ์ 3๋ฒ์ผ๋ก ์ฎ๊ธฐ๋ฉด ๋๋ค. ์์ค ์ฝ๋ #include using namespace std; void fun..
-
[C++] DFS(Depth First Search) ๊น์ด ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆAlgorithm & Data Structure 2022. 1. 30. 15:19
๋ค์ด๊ฐ๋ฉฐ DFS๋ ์์์ ๋ฐฐ์ด BFS์ฒ๋ผ ํ์ ์๊ณ ๋ฆฌ์ฆ ์ค ํ๋์ด๋ค. BFS์ ๊ตฌํ์ ์ฐจ์ด์ ์ด ์๋ค๋ฉด BFS์์๋ Queue(ํ)๋ฅผ ์ฌ์ฉ ํ์ง๋ง, DFS์์๋ Stack(์คํ)์ ์ฌ์ฉํด์ ๊ตฌํํ๋ค. DFS(๊น์ด ์ฐ์ ํ์) ์ด๋? ๊น์ด ์ฐ์ ํ์( - ๅชๅ ๆข็ดข, ์์ด: depth-first search, DFS)์ ๋งน๋ชฉ์ ํ์๋ฐฉ๋ฒ์ ํ๋๋ก ํ์ํธ๋ฆฌ์ ์ต๊ทผ์ ์ฒจ๊ฐ๋ ๋ ธ๋๋ฅผ ์ ํํ๊ณ , ์ด ๋ ธ๋์ ์ ์ฉ ๊ฐ๋ฅํ ๋์์ ์ค ํ๋๋ฅผ ์ ์ฉํ์ฌ ํธ๋ฆฌ์ ๋ค์ ์์ค(level)์ ํ ๊ฐ์ ์์๋ ธ๋๋ฅผ ์ฒจ๊ฐํ๋ฉฐ, ์ฒจ๊ฐ๋ ์์ ๋ ธ๋๊ฐ ๋ชฉํ๋ ธ๋์ผ ๋๊น์ง ์์ ์์ ๋ ธ๋์ ์ฒจ๊ฐ ๊ณผ์ ์ ๋ฐ๋ณตํด ๊ฐ๋ ๋ฐฉ์์ด๋ค. - ์ํค๋ฐฑ๊ณผ DFS ์๊ณ ๋ฆฌ์ฆ ์๋์ ์ฌ์ง๋ค์ ๋ณด๊ณ DFS๋ฅผ ์ดํดํด๋ณด์. ์์ ์ง์ ์ 1์ด๋ผ๊ณ ํ์. 1์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ..
-
[๋ฐฑ์ค(BOJ) 1697๋ฒ] ์จ๋ฐ๊ผญ์ง (C++)PS(Problem Solving)/C++ 2022. 1. 30. 14:37
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1697 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ ๋ฒ์งธ ์ค์ ์๋น์ด๊ฐ ์๋ ์์น N๊ณผ ๋์์ด ์๋ ์์น K๊ฐ ์ฃผ์ด์ง๋ค. N๊ณผ K๋ ์ ์์ด๋ค. ์ถ๋ ฅ ์๋น์ด๊ฐ ๋์์ ์ฐพ๋ ๊ฐ์ฅ ๋น ๋ฅธ ์๊ฐ์ ์ถ๋ ฅํ๋ค. ํ์ด ์ด ๋ฌธ์ ๋ BFS์ ์์ฉ ๋ฌธ์ ๋ก 1์ฐจ์์์์ BFS๋ฅผ ๋๋ฆฌ๋ ๋ฌธ์ ์ด๋ค. ์์ค ์ฝ๋ #include using namespace std; #define X first #define Y second int dist[100002]; int n, k; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; fill(dist, dist + 100002, -1); queue Q; Q.push(n); di..
-
[๋ฐฑ์ค(BOJ) 4179๋ฒ] ๋ถ! (C++)PS(Problem Solving)/C++ 2022. 1. 30. 14:23
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/4179 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ ๋ ฅ์ ์ฒซ์งธ ์ค์๋ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋ ๋ ์ ์ R๊ณผ C๊ฐ ์ฃผ์ด์ง๋ค. ๋จ, 1 ≤ R, C ≤ 1000 ์ด๋ค. R์ ๋ฏธ๋ก ํ์ ๊ฐ์, C๋ ์ด์ ๊ฐ์์ด๋ค. ๋ค์ ์ ๋ ฅ์ผ๋ก R์ค๋์ ๊ฐ๊ฐ์ ๋ฏธ๋ก ํ์ด ์ฃผ์ด์ง๋ค. ๊ฐ๊ฐ์ ๋ฌธ์๋ค์ ๋ค์์ ๋ปํ๋ค. #: ๋ฒฝ .: ์ง๋๊ฐ ์ ์๋ ๊ณต๊ฐ J: ์งํ์ด์ ๋ฏธ๋ก์์์ ์ด๊ธฐ์์น (์ง๋๊ฐ ์ ์๋ ๊ณต๊ฐ) F: ๋ถ์ด ๋ ๊ณต๊ฐ J๋ ์ ๋ ฅ์์ ํ๋๋ง ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์งํ์ด๊ฐ ๋ถ์ด ๋๋ฌํ๊ธฐ ์ ์ ๋ฏธ๋ก๋ฅผ ํ์ถ ํ ์ ์๋ ๊ฒฝ์ฐ IMPOSSIBLE ์ ์ถ๋ ฅํ๋ค. ์งํ์ด๊ฐ ๋ฏธ๋ก๋ฅผ ํ์ถํ ์ ์๋ ๊ฒฝ์ฐ์๋ ๊ฐ์ฅ ๋น ๋ฅธ ํ์ถ์๊ฐ์ ์ถ๋ ฅํ๋ค. ํ์ด ์ด ๋ฌธ์ ๋ BFS์ ์์ฉ ๋ฌธ์ ๋ก ์์์ ์ด ๋ ์ข ๋ฅ์ผ ๋ ํด๊ฒฐ..
-
[๋ฐฑ์ค(BOJ) 7576๋ฒ] ํ ๋งํ (C++)PS(Problem Solving)/C++ 2022. 1. 23. 23:35
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7576 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ ์ค์๋ ์์์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ๋ ์ ์ M,N์ด ์ฃผ์ด์ง๋ค. M์ ์์์ ๊ฐ๋ก ์นธ์ ์, N์ ์์์ ์ธ๋ก ์นธ์ ์๋ฅผ ๋ํ๋ธ๋ค. ๋จ, 2 ≤ M,N ≤ 1,000 ์ด๋ค. ๋์งธ ์ค๋ถํฐ๋ ํ๋์ ์์์ ์ ์ฅ๋ ํ ๋งํ ๋ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ์ฆ, ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ์์์ ๋ด๊ธด ํ ๋งํ ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ํ๋์ ์ค์๋ ์์ ๊ฐ๋ก์ค์ ๋ค์ด์๋ ํ ๋งํ ์ ์ํ๊ฐ M๊ฐ์ ์ ์๋ก ์ฃผ์ด์ง๋ค. ์ ์ 1์ ์ต์ ํ ๋งํ , ์ ์ 0์ ์ต์ง ์์ ํ ๋งํ , ์ ์ -1์ ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์ ์นธ์ ๋ํ๋ธ๋ค. ํ ๋งํ ๊ฐ ํ๋ ์ด์ ์๋ ๊ฒฝ์ฐ๋ง ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฌ๋ฌ๋ถ์ ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์ ๋๊น์ง์ ์ต์ ๋ ์ง๋ฅผ ์ถ๋ ฅํด์ผ ํ๋ค. ๋ง..
-
[๋ฐฑ์ค(BOJ) 2178๋ฒ] ๋ฏธ๋ก ํ์ (C++)PS(Problem Solving)/C++ 2022. 1. 23. 23:17
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/2178 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๋ ์ ์ N, M(2 ≤ N, M ≤ 100)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ M๊ฐ์ ์ ์๋ก ๋ฏธ๋ก๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ๊ฐ์ ์๋ค์ ๋ถ์ด์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ง๋์ผ ํ๋ ์ต์์ ์นธ ์๋ฅผ ์ถ๋ ฅํ๋ค. ํญ์ ๋์ฐฉ์์น๋ก ์ด๋ํ ์ ์๋ ๊ฒฝ์ฐ๋ง ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค. ํ์ด ์ด ๋ฌธ์ ๋ BFS์ ์์ฉ ๋ฌธ์ ๋ก ๋ค์ฐจ์ ๋ฐฐ์ด์์์ ๊ฑฐ๋ฆฌ ์ธก์ ๋ฌธ์ ๋ค! ์์ค ์ฝ๋ #include using namespace std; #define X first #define Y second string board[102]; int dist[102][102]; // ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ ๋ฐฐ์ด int n, m; int dx[4] = { 1, ..
-
[๋ฐฑ์ค(BOJ) 1926๋ฒ] ๊ทธ๋ฆผ (C++)PS(Problem Solving)/C++ 2022. 1. 21. 23:14
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1926 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๋ํ์ง์ ์ธ๋ก ํฌ๊ธฐ n(1 ≤ n ≤ 500)๊ณผ ๊ฐ๋ก ํฌ๊ธฐ m(1 ≤ m ≤ 500)์ด ์ฐจ๋ก๋ก ์ฃผ์ด์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ n+1 ์ค ๊น์ง ๊ทธ๋ฆผ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. (๋จ ๊ทธ๋ฆผ์ ์ ๋ณด๋ 0๊ณผ 1์ด ๊ณต๋ฐฑ์ ๋๊ณ ์ฃผ์ด์ง๋ฉฐ, 0์ ์์น ์ด ์๋ ๋ถ๋ถ, 1์ ์์น ์ด ๋ ๋ถ๋ถ์ ์๋ฏธํ๋ค) ์ถ๋ ฅ ์ฒซ์งธ ์ค์๋ ๊ทธ๋ฆผ์ ๊ฐ์, ๋์งธ ์ค์๋ ๊ทธ ์ค ๊ฐ์ฅ ๋์ ๊ทธ๋ฆผ์ ๋์ด๋ฅผ ์ถ๋ ฅํ์ฌ๋ผ. ๋จ, ๊ทธ๋ฆผ์ด ํ๋๋ ์๋ ๊ฒฝ์ฐ์๋ ๊ฐ์ฅ ๋์ ๊ทธ๋ฆผ์ ๋์ด๋ 0์ด๋ค. ํ์ด ์ด์ค for๋ฌธ์ ํตํด ์์์ขํ๋ฅผ ๊ตฌํ๋ ๋ฐฉ๋ฒ์ ์๊ณ ์์ผ๋ฉด BFS ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํด๊ฒฐํ ์ ์๋ค. ์์ค ์ฝ๋ #include using namespace std; #defin..
-
[C++] BFS(Breadth First Search) ๋๋น ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆAlgorithm & Data Structure 2022. 1. 21. 23:01
๋ค์ด๊ฐ๋ฉฐ BFS๋ ์ฝ๋ฉํ ์คํธ์ ์์ฃผ ์ฌ์ฉ๋๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. Flood Fill๊ณผ ๊ฐ์ ๋ฌธ์ ๋ค์ ํด๊ฒฐํ๋ ๋ฐ ์ฌ์ฉํ ์ ์๋ค. ์ด๋ฅผ ๊ตฌํํ๊ธฐ ์ํด์๋ Queue(ํ)๋ฅผ ์ฌ์ฉํ๋ค! BFS(๋๋น ์ฐ์ ํ์) ์ด๋? ๋๋น ์ฐ์ ํ์(Breadth-first search, BFS)์ ๋งน๋ชฉ์ ํ์๋ฐฉ๋ฒ์ ํ๋๋ก ์์ ์ ์ ์ ๋ฐฉ๋ฌธํ ํ ์์ ์ ์ ์ ์ธ์ ํ ๋ชจ๋ ์ ์ ๋ค์ ์ฐ์ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ๋ฒ์ด๋ค. ๋ ์ด์ ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ด ์์ ๋๊น์ง ๋ฐฉ๋ฌธํ์ง ์์ ๋ชจ๋ ์ ์ ๋ค์ ๋ํด์๋ ๋๋น ์ฐ์ ๊ฒ์์ ์ ์ฉํ๋ค. OPEN List๋ ํ๋ฅผ ์ฌ์ฉํด์ผ๋ง ๋ ๋ฒจ ์์๋๋ก ์ ๊ทผ์ด ๊ฐ๋ฅํ๋ค. - ์ํค๋ฐฑ๊ณผ BFS ์๊ณ ๋ฆฌ์ฆ ์๋์ ์ฌ์ง๋ค์ ๋ณด๊ณ BFS๋ฅผ ์ดํดํด๋ณด์. ์์ ์ง์ ์ด 1์ด๋ผ๊ณ ํ์. ๊ทธ๋ฌ๋ฉด 1์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํด๋น ์นธ์ ํ์..