โ๏ธ ์ฝํ
์ค๋น/DFS, BFS
๋ณธ ๊ฒ์๊ธ์ PC๋ฒ์ ์ ์ต์ ํ ๋์ด์์ต๋๋ค. www.acmicpc.net/problem/1260 1260๋ฒ: DFS์ BFS ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 โค N โค 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 โค M โค 10,000), ํ์์ ์์ํ ์ ์ ์ ๋ฒํธ V๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ๊ฐ์ ์ด ์ฐ๊ฒฐํ๋ ๋ ์ ์ ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ค ๋ ์ ์ ์ฌ www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 โค N โค 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 โค M โค 10,000), ํ์์ ์์ํ ์ ์ ์ ๋ฒํธ V๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ๊ฐ์ ์ด ์ฐ๊ฒฐํ๋ ๋ ์ ์ ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ค ๋ ์ ์ ์ฌ์ด์ ์ฌ๋ฌ ๊ฐ์ ๊ฐ์ ์ด ์์ ์ ์๋ค. ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๊ฐ์ ์ ์๋ฐฉํฅ์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ DFS๋ฅผ..
โ๏ธ ์ฝํ
์ค๋น/DFS, BFS
www.acmicpc.net/problem/1707 1707๋ฒ: ์ด๋ถ ๊ทธ๋ํ ์
๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ
์คํธ ์ผ์ด์ค๋ก ๊ตฌ์ฑ๋์ด ์๋๋ฐ, ์ฒซ์งธ ์ค์ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์ K(2โคKโค5)๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ๊ทธ๋ํ์ ์ ์ ์ ๊ฐ์ V(1โคVโค20,000)์ ๊ฐ์ ์ ๊ฐ์ www.acmicpc.net ์
๋ ฅ ์
๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ
์คํธ ์ผ์ด์ค๋ก ๊ตฌ์ฑ๋์ด ์๋๋ฐ, ์ฒซ์งธ ์ค์ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์ K(2โคKโค5)๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ๊ทธ๋ํ์ ์ ์ ์ ๊ฐ์ V(1โคVโค20,000)์ ๊ฐ์ ์ ๊ฐ์ E(1โคEโค200,000)๊ฐ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์์๋๋ก ์ฃผ์ด์ง๋ค. ๊ฐ ์ ์ ์๋ 1๋ถํฐ V๊น์ง ์ฐจ๋ก๋ก ๋ฒํธ๊ฐ ๋ถ์ด ์๋ค. ์ด์ด์ ๋์งธ ์ค๋ถํฐ E๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ์ ์ ๋ํ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋๋ฐ..
โ๏ธ ์ฝํ
์ค๋น/DFS, BFS
www.acmicpc.net/problem/7562 7562๋ฒ: ๋์ดํธ์ ์ด๋ ์ฒด์คํ ์์ ํ ๋์ดํธ๊ฐ ๋์ฌ์ ธ ์๋ค. ๋์ดํธ๊ฐ ํ ๋ฒ์ ์ด๋ํ ์ ์๋ ์นธ์ ์๋ ๊ทธ๋ฆผ์ ๋์์๋ค. ๋์ดํธ๊ฐ ์ด๋ํ๋ ค๊ณ ํ๋ ์นธ์ด ์ฃผ์ด์ง๋ค. ๋์ดํธ๋ ๋ช ๋ฒ ์์ง์ด๋ฉด ์ด ์นธ์ผ๋ก ์ด๋ํ ์ www.acmicpc.net ์
๋ ฅ ์
๋ ฅ์ ์ฒซ์งธ ์ค์๋ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ ์ธ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์ฒซ์งธ ์ค์๋ ์ฒด์คํ์ ํ ๋ณ์ ๊ธธ์ด l(4 โค l โค 300)์ด ์ฃผ์ด์ง๋ค. ์ฒด์คํ์ ํฌ๊ธฐ๋ l ร l์ด๋ค. ์ฒด์คํ์ ๊ฐ ์นธ์ ๋ ์์ ์ {0, ..., l-1} ร {0, ..., l-1}๋ก ๋ํ๋ผ ์ ์๋ค. ๋์งธ ์ค๊ณผ ์
์งธ ์ค์๋ ๋์ดํธ๊ฐ ํ์ฌ ์๋ ์นธ, ๋์ดํธ๊ฐ ์ด๋ํ๋ ค๊ณ ํ๋ ์นธ์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ๊ฐ ํ
..
โ๏ธ ์ฝํ
์ค๋น/DFS, BFS
www.acmicpc.net/problem/2206 2206๋ฒ: ๋ฒฝ ๋ถ์๊ณ ์ด๋ํ๊ธฐ NรM์ ํ๋ ฌ๋ก ํํ๋๋ ๋งต์ด ์๋ค. ๋งต์์ 0์ ์ด๋ํ ์ ์๋ ๊ณณ์ ๋ํ๋ด๊ณ , 1์ ์ด๋ํ ์ ์๋ ๋ฒฝ์ด ์๋ ๊ณณ์ ๋ํ๋ธ๋ค. ๋น์ ์ (1, 1)์์ (N, M)์ ์์น๊น์ง ์ด๋ํ๋ ค ํ๋๋ฐ, ์ด๋ ์ต๋จ ๊ฒฝ๋ก www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ N(1 โค N โค 1,000), M(1 โค M โค 1,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์ M๊ฐ์ ์ซ์๋ก ๋งต์ด ์ฃผ์ด์ง๋ค. (1, 1)๊ณผ (N, M)์ ํญ์ 0์ด๋ผ๊ณ ๊ฐ์ ํ์. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅํ๋ค. ๋ถ๊ฐ๋ฅํ ๋๋ -1์ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ ์ต๋จ ๊ฒฝ๋ก ๋ฌธ์ ์ด๋ค. ์ด ๋ฌธ์ ๋ฅผ ์ฒ์ ์ ํ์ ๋๋ DFS๋ก ํ์ด์ผํ๋ ์ค ์์๋ค. ๋ฒฝ์ ๋ถ์
จ๋์ง ํ์ธํ๋ bool..