์๊ณ ๋ฆฌ์ฆ24 [๋ฐฑ์ค 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. ๋ฐฑ์ค 14500๋ฒ ํ ํธ๋ก๋ฏธ๋ ธ ์์ ํ์(brute-force) ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ :: ์ฝ๋์๋ชฝ [๋ฐฑ์ค] 14500๋ฒ ํ ํธ๋ก๋ฏธ๋ ธ 14500๋ฒ: ํ ํธ๋ก๋ฏธ๋ ธ ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํฌ๊ธฐ๊ฐ 1ร1์ธ ์ ์ฌ๊ฐํ์ ์ฌ๋ฌ ๊ฐ ์ด์ด์ ๋ถ์ธ ๋ํ์ด๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ์๋ก ๊ฒน์น๋ฉด ์ ๋๋ค. ๋ํ์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ๋ณ๋ผ๋ฆฌ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ฆ, ๊ผญ์ง์ ๊ณผ ๊ผญ์ง์ ๋ง ๋ง๋ฟ์ ์์ผ๋ฉด ์ ๋๋ค. ์ ์ฌ๊ฐํ 4๊ฐ๋ฅผ ์ด์ด ๋ถ์ธ ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํ ํธ๋ก๋ฏธ๋ ธ๋ผ๊ณ ํ๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ 5๊ฐ์ง๊ฐ ์๋ค. ์๋ฆ์ด๋ ํฌ๊ธฐ๊ฐ NรM์ธ ์ข ์ด ์์ ํ ํธ๋ก๋ฏธ๋ ธ ํ๋๋ฅผ ๋์ผ๋ ค๊ณ ํ๋ค. ์ข ์ด๋ 1ร1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋ www.acmicpc.net ํ์ด ์ด๋ฐ ๋ธ๋ก ํํ์ ๋ฌธ์ ๊ฐ ๋์ค๋ฉด ์ค์ ๋ก ๋ํ์ ๊ทธ๋ ค๋ณด๋ฉด์ ๋ฌธ์ ๋ฅผ ํธ๋ ๊ฒ์ด ๊ฐ์ฅ ์ข์ ๋ฐฉ๋ฒ์ธ ๊ฒ ๊ฐ๋ค. ๋จผ์ N*M ํฌ๊ธฐ์ ์ข ์ด ์์ ๋ธ๋ก ํ๋๋ง ๋๋๋ค๊ณ ํ์ผ๋.. 2019. 12. 23. ์ด์ 1 2 ๋ค์