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

๋ฐฑ์ค€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.