๋ฐฑ์ค4 ๋ฐฑ์ค 2839 ํ์ด์ฌ - ์คํ ๋ฐฐ๋ฌ - ๋์ ๊ณํ๋ฒ ๋ฐฑ์ค 2839 ํ์ด์ฌ https://www.acmicpc.net/problem/2839 2839๋ฒ: ์คํ ๋ฐฐ๋ฌ ์๊ทผ์ด๋ ์์ฆ ์คํ๊ณต์ฅ์์ ์คํ์ ๋ฐฐ๋ฌํ๊ณ ์๋ค. ์๊ทผ์ด๋ ์ง๊ธ ์ฌํ๊ฐ๊ฒ์ ์คํ์ ์ ํํ๊ฒ Nํฌ๋ก๊ทธ๋จ์ ๋ฐฐ๋ฌํด์ผ ํ๋ค. ์คํ๊ณต์ฅ์์ ๋ง๋๋ ์คํ์ ๋ด์ง์ ๋ด๊ฒจ์ ธ ์๋ค. ๋ด์ง๋ 3ํฌ๋ก๊ทธ www.acmicpc.net Nํฌ๋ก๊ทธ๋จ์ ์คํ์ด ์ฃผ์ด์ก์ ๋, ์คํ์ ๋ด๊ธฐ ์ํด 3ํค๋ก๊ทธ๋จ๊ณผ 5ํค๋ก๊ทธ๋จ ๋ด์ง๋ก ๊ฐ์ฅ ์ ์ ์์ ๋ด์ง๋ฅผ ๋ง๋ค์ด ๋ด๋ ๋ฐฉ๋ฒ์ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. ์ด ๋ฌธ์ ๋ ๊ณ์ฐ ํ์๋ฅผ ์ค์ด๊ธฐ ์ํด ์ด์ ์ ๊ณ์ฐํ๋ ๊ฐ์ ๊ธฐ์ตํด๋๋ค๊ฐ ์ฌ์ฌ์ฉํ๋ ๋ฉ๋ชจ์ด์ ์ด์ ์ ํ์ฉํ๋ ๊ฒ์ด ์ ๋นํ๋ค๊ณ ํ๋จํ์ต๋๋ค. 3 ~ Nํฌ๋ก๊ทธ๋จ๊น์ง ์์ ์ซ์๋ถํฐ... ๊ฐ๊ฐ ๊ฐ์ฅ ์ ์ ์์ ๋ด์ง๋ฅผ ์ ์ฅํด๋๋ฉด... ํด๋น ๊ฐ๋ณด๋ค 3, 5 ํฐ .. 2021. 10. 5. [๋ฐฑ์ค 11724 ์ฐ๊ฒฐ ์์์ ๊ฐ์] ํ์ด์ฌ BFS ๋๋น ์ฐ์ ํ์ ํ์ด ์ฐ๊ฒฐ ์์์ ๊ฐ์ ๋ฌธ์ 11724๋ฒ: ์ฐ๊ฒฐ ์์์ ๊ฐ์ ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N๊ณผ ๊ฐ์ ์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. (1 โค N โค 1,000, 0 โค M โค Nร(N-1)/2) ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ๊ฐ์ ์ ์ ๋์ u์ v๊ฐ ์ฃผ์ด์ง๋ค. (1 โค u, v โค N, u โ v) ๊ฐ์ ๊ฐ์ ์ ํ ๋ฒ๋ง ์ฃผ๏ฟฝ๏ฟฝ www.acmicpc.net ๋ฑกํฅ ์์ ์๋ฐฉํฅ ๊ทธ๋ํ๊ฐ ์ฃผ์ด์ก์ ๋ ์ฐ๊ฒฐ ์์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค. ๋ฌธ์ ํ์ด ์ฐ๊ฒฐ ์์๋ฅผ ๊ตฌํ๋ ๊ฒ์ ์ฆ ๋ช๊ฐ์ ๊ตฌ์ญ์ผ๋ก ๋๋์ด์ ธ ์๋์ง ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค. ๊ทธ๋ํ๋ฅผ ์์ ๊ฐ์ด ํํํ์๋ 2๊ฐ์ ์์ญ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค. DFS, BFS ๋ชจ๋ ์ฌ์ฉํด์ ํ์ ์๋ ๋ฌธ์ ์ ๋๋ค. ๋๋น ์ฐ์ ํ์ BFS๋ก ๋ฌธ์ ๋ฅผ ํ์ด๋ณด๊ฒ ์ต๋๋ค. 1. ๊ทธ๋ํ ์ฐ๊ฒฐ ์ ๋ณด์ฉ ํ๋ ฌ ์์ฑ 2. BFS.. 2020. 9. 28. [๋ฐฑ์ค 1012 ์ ๊ธฐ๋ ๋ฐฐ์ถ] ํ์ด์ฌ BFS ๋๋น ์ฐ์ ํ์ ํ์ด ์ ๊ธฐ๋ ๋ฐฐ์ถ ๋ฌธ์ 1012๋ฒ: ์ ๊ธฐ๋ ๋ฐฐ์ถ ์ฐจ์ธ๋ ์๋์ธ ํ๋๋ ๊ฐ์๋ ๊ณ ๋ญ์ง์์ ์ ๊ธฐ๋ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๊ธฐ๋ก ํ์๋ค. ๋์ฝ์ ์ฐ์ง ์๊ณ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๋ ค๋ฉด ๋ฐฐ์ถ๋ฅผ ํด์ถฉ์ผ๋ก๋ถํฐ ๋ณดํธํ๋ ๊ฒ์ด ์ค์ํ๊ธฐ ๋๋ฌธ์, ํ๋๋ ํด์ถฉ ๋ฐฉ์ง์ ๏ฟฝ www.acmicpc.net 2์ฐจ์ ๋ฐฐ์ด์ ์ ๊ธฐ๋ ๋ฐฐ์ถ๋ฐญ์ด ์ฃผ์ด์ง๊ณ 0(๋ ) ๊ณผ 1(๋ฐฐ์ถ ์ฌ์ด์ ธ ์๋ ๋ )๋ก ๋ฐ์ดํฐ๊ฐ ๊ตฌ๋ถ๋ฉ๋๋ค. ๋ฐฐ์ถํฐ ์ง๋ ์ด๋ฅผ ๋ฐฐ์ถ์ ์์ํ๊ฒ ํ๋ฉด ์ฌ๋ฐฉ๋ฉด์ผ๋ก ์ด๋์ด ๊ฐ๋ฅํ์ฌ ๋ค๋ฅธ ๋ฐฐ์ถ๋ฅผ ํด์ถฉ์ผ๋ก๋ถํฐ ๋ณดํธ๊ฐ ๊ฐ๋ฅํ๋ค. ํ์ํ ๋ฐฐ์ถํฐ ์ง๋ ์ด์ ๋ง๋ฆฌ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค. ์ ๋ ฅ ๋ฐ๋ ์ ๋ณด๋ก ์๋์ ๊ฐ์ด ๋ฐฐ์ถ ๋ฐญ์ 2์ฐจ์ ๋ฐฐ์ด ํํ๋ก ๋ง๋ค์ด ์ฃผ์ด์ผ ํฉ๋๋ค. ๋ฌธ์ ํ์ด 4๋ฐฉ๋ฉด์ผ๋ก ์ด๋์ด ๊ฐ๋ฅํ๋ฏ๋ก ๊ฐ ์์ญ๋น ํ๋ง๋ฆฌ์ ๋ฐฐ์ถํฐ ์ง๋ ์ด๋ฅผ ๋ฐฐ์นํ๋ฉด ํด๊ฒฐํ ์ ์์ต๋๋ค. ์ฆ, .. 2020. 9. 28. [๋ฐฑ์ค 10026 ์ ๋ก์์ฝ] ํ์ด์ฌ BFS ๋๋น ์ฐ์ ํ์ ํ์ด ์ ๋ก์์ฝ ๋ฌธ์ 10026๋ฒ: ์ ๋ก์์ฝ ์ ๋ก์์ฝ์ ๋นจ๊ฐ์๊ณผ ์ด๋ก์์ ์ฐจ์ด๋ฅผ ๊ฑฐ์ ๋๋ผ์ง ๋ชปํ๋ค. ๋ฐ๋ผ์, ์ ๋ก์์ฝ์ธ ์ฌ๋์ด ๋ณด๋ ๊ทธ๋ฆผ์ ์๋ ์ฌ๋์ด ๋ณด๋ ๊ทธ๋ฆผ๊ณผ๋ ์ข ๋ค๋ฅผ ์ ์๋ค. ํฌ๊ธฐ๊ฐ NรN์ธ ๊ทธ๋ฆฌ๋์ ๊ฐ ์นธ์ R(๋นจ๊ฐ), G(์ด๋ก) www.acmicpc.net RGB 3๊ฐ์ง ๋ฌธ์๋ก ์ด๋ฃจ์ด์ง N * N ๋ณด๋ํ์ด ์ฃผ์ด์ง๋ ์ผ๋ฐ์ฌ๋๊ณผ ์ ๋ก์์ฝ์ธ ์ฌ๋์ด ๋ณด๋ ๊ตฌ์ญ์ ์๋ฅผ ๊ฐ๊ฐ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค. ์ ๋ก์์ฝ์ R๊ณผ G๋ฅผ ํ๋์ ์์ผ๋ก ๋ณด์ ๋๋ค. ์ฆ, ์๋์ ๊ฐ์ด ๊ตฌ์ญ์ด ๋๋๊ฒ ๋ฉ๋๋ค. ๋ฌธ์ ํ์ด 2์ฐจ์ ๋ฐฐ์ด์ ์์ญ์ ๊ตฌํ๋ ๋ฌธ์ ๋ก BFS ๋๋น ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ ํ๋ฉด ๋ ๊ฒ์ผ๋ก ํ๋จํ์ต๋๋ค. ๋จ, 2๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ๋ฐ์ํ๊ธฐ ๋๋ฌธ์ 2๊ฐ์ง ๋ฒ์ ์ ๋ฐฐ์ด์ ๋ง๋ค์ด์ฃผ๊ณ ํ์ํ๋ ๋ฐฉ์์ ์ ํํ์ต๋๋ค. N์ ์ต๋ .. 2020. 9. 27. ์ด์ 1 ๋ค์