๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜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.