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

๐Ÿ”Ž Algorithm/๐Ÿ’ป ๋ฌธ์ œ ํ’€์ด16

[๋ฐฑ์ค€] 1520. ๋‚ด๋ฆฌ๋ง‰๊ธธ ๋ฌธ์ œ ํ’€์ด ๋จผ์ € ๋ชจ๋“  ๊ฒฝ๋กœ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•ด์•ผํ•˜๊ธฐ ๋•Œ๋ฌธ์— DFS๋ฅผ ์‚ฌ์šฉํ•ด ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ–ˆ๋‹ค. ํ•˜์ง€๋งŒ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํƒ์ƒ‰ํ•˜๊ฒŒ ๋˜๋Š” ๊ฒฝ์šฐ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ด๋ฅผ ์ค„์ด๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์ด ํ•„์š”ํ•˜๋‹ค. ์ƒ๊ฐํ•œ ์•„์ด๋””์–ด๋Š” ํ•œ ๋ฒˆ ๋ฐฉ๋ฌธํ–ˆ๋˜ ์ขŒํ‘œ๋ฅผ x,y๋ผ๊ณ  ํ–ˆ์„ ๋•Œ, (x,y) ์—์„œ (N-1, N-1)๊นŒ์ง€์˜ ๊ฒฝ๋กœ๋Š” ์ด๋ฏธ ๊ตฌํ•ด์ ธ์žˆ๊ณ  ๋ณ€ํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค์‹œ ํƒ์ƒ‰ํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค๋Š” ์ ์ด๋‹ค. ๋”ฐ๋ผ์„œ dfs๋ฅผ ์ง„ํ–‰ํ•˜๋ฉฐ ๋ฐฉ๋ฌธ์ฒดํฌ๋ฅผ ํ•˜๊ณ , ๋ฐฉ๋ฌธ์ฒดํฌ๊ฐ€ ๋œ ๊ณณ์ธ ๊ฒฝ์šฐ ์ €์žฅ๋˜์–ด ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ทธ๋Œ€๋กœ ์‚ฌ์šฉํ•จ์œผ๋กœ์จ ์‹œ๊ฐ„์„ ์ค„์ผ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ์ฃผ์˜ํ•  ์ ์ด ์žˆ๋‹ค. ์ดˆ๊ธฐ ์ž‘์„ฑํ•œ ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu.. 2021. 4. 1.
[๋ฐฑ์ค€] 2629. ์–‘ํŒ” ์ €์šธ ๋ฌธ์ œ ํ’€์ด ์˜ค๋žœ๋งŒ์— ํ‘ธ๋Š” DP๋ฌธ์ œ์˜€๋‹ค. ๋จผ์ € ์ถ”๋ฅผ ๋„ฃ์—ˆ์„ ๋•Œ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ์ถ”์˜ ๋ฌด๊ฒŒ๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ Cache๋ฐฐ์—ด์„ ์œ ์ง€ํ–ˆ๋‹ค. ์ด ๋•Œ ํ•ด๋‹น ์ถ”์— ๋Œ€ํ•ด ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ ์ˆ˜๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ํ˜„์žฌ ์ถ”๋งŒ ๋„ฃ์€ ๊ฒฝ์šฐ ์ด์ „ ๋‹จ๊ณ„์—์„œ ๋งŒ๋“ค์—ˆ๋˜ ๋ฌด๊ฒŒ๋ฅผ ๊ทธ๋Œ€๋กœ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ ์ด์ „ ๋‹จ๊ณ„์—์„œ ๋งŒ๋“ค์—ˆ๋˜ ๋ฌด๊ฒŒ์— ํ˜„์žฌ ์ถ”๋ฅผ ๋”ํ•˜๋Š” ๊ฒฝ์šฐ ์ด์ „ ๋‹จ๊ณ„์—์„œ ๋งŒ๋“ค์—ˆ๋˜ ๋ฌด๊ฒŒ์— ํ˜„์žฌ ์ถ”๋ฅผ ๋นผ๋Š” ๊ฒฝ์šฐ (๋ฌผ์ฒด์ชฝ์— ์ถ”๋ฅผ ๋†“๋Š” ๊ฒฝ์šฐ) ์ตœ์ข…์ ์œผ๋กœ ๋งˆ์ง€๋ง‰ ์ถ”๋ฅผ ๋„ฃ์—ˆ์„ ๋•Œ ๊ฐ€๋Šฅํ•œ ๋ฌด๊ฒŒ๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { // Input ๋ฐ›๊ธฐ ์œ„ํ•œ Buffered Re.. 2021. 4. 1.
[๋ฐฑ์ค€] - 2206. ๋ฒฝ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ ๋ฌธ์ œ ํ’€์ด ์ด ๋ฌธ์ œ๋Š” ์˜ˆ์ „์— BFS๋ฅผ ํ•œ์ฐฝ ํ’€์—ˆ์„ ๋•Œ์—๋Š” ๋ชป ํ’€์—ˆ๋˜ ๋ฌธ์ œ์˜€๋Š”๋ฐ ์ด์™€ ์œ ์‚ฌํ•œ ๋ฌธ์ œ์ธ 1600. ๋ง์ด ๋˜๊ณ ํ”ˆ ์›์ˆญ์ด๋ฌธ์ œ๋ฅผ ํ’€๊ณ  ์˜๊ฐ์„ ์–ป์–ด์„œ ๋‹ค์‹œ ๋„์ „ํ–ˆ๋”๋‹ˆ ์‰ฝ๊ฒŒ ํ’€๋ ธ๋‹ค. ์ด ๋ฌธ์ œ๊ฐ€ ์ผ๋ฐ˜์ ์ธ BFS๋ณด๋‹ค ๊นŒ๋‹ค๋กœ์šด ์ด์œ ๋Š” ์–ด๋–ค ์ขŒํ‘œ์— ์˜ฌ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ 2๊ฐ€์ง€(์ด์ „์— ๋ฒฝ์„ ๋ถ€์‹  ๊ฒฝ์šฐ, ์ด์ „์— ๋ฒฝ์„ ๋ถ€์ˆ˜์ง€ ์•Š์€ ๊ฒฝ์šฐ)๋ผ๋Š” ์ ์ด๋‹ค. ๋”ฐ๋ผ์„œ 2์ฐจ์› ๋ฐฉ๋ฌธ ๋ฐฐ์—ด๋กœ๋Š” ์ฒ˜๋ฆฌ๊ฐ€ ๋ถˆ๊ฐ€๋Šฅํ•˜๊ณ  3์ฐจ์› ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜์˜€๋‹ค. 3์ฐจ์› ๋ฐฐ์—ด์—์„œ 0๋ฒˆ์จฐ ์ธ๋ฑ์Šค๋Š” ๋ฒฝ์„ ์ด๋ฏธ ๋ถ€์ˆ˜๊ณ  ์˜จ ๊ฒฝ์šฐ, 1๋ฒˆ์งธ ์ธ๋ฑ์Šค๋Š” ๋ฒฝ์„ ์•„์ง ๋ถ€์ˆ˜์ง€ ์•Š์€ ๊ฒฝ์šฐ์ด๋‹ค. bfs๋ฅผ ์ง„ํ–‰ํ•˜๋ฉฐ ๋‹ค์Œ์˜ 3๊ฐ€์ง€ ๊ฒฝ์šฐ์— ๋Œ€ํ•ด์„œ ์ฒ˜๋ฆฌํ•ด์ฃผ์—ˆ๋‹ค. ํ˜„์žฌ ๋ฒฝ์„ ๋ถ€์ˆ  ์ˆ˜ ์žˆ๋Š” ๊ธฐํšŒ๊ฐ€ ๋‚จ์•„์žˆ๊ณ  ๋‹ค์Œ ๋ฐฉ๋ฌธํ•  ์ขŒํ‘œ๊ฐ€ ๋ฒฝ์ธ ๊ฒฝ์šฐ, ๊ธฐํšŒ๋ฅผ ์†Œ์ง„ํ•˜๊ณ  ๋ฒฝ์„ ๋ฐฉ๋ฌธ ๊ธฐํšŒ๊ฐ€.. 2021. 3. 24.
[๋ฐฑ์ค€] - 1277. ๋ฐœ์ „์†Œ ์„ค์น˜ ๋ฌธ์ œ ํ’€์ด 1๋ฒˆ ๋ฐœ์ „์†Œ๋ถ€ํ„ฐ N๋ฒˆ์งธ ๋ฐœ์ „์†Œ๊นŒ์ง€์˜ ์ตœ์†Œ ๋น„์šฉ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•˜์˜€๋‹ค. ๋จผ์ € ๊ฐ ๋ฐœ์ „์†Œ์˜ ์ขŒํ‘œ๋ฅผ ์ €์žฅ(plant)ํ•˜๊ณ , ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š”์ง€ ์—ฌ๋ถ€๋ฅผ ์ €์žฅ(connected)ํ•˜์˜€๋‹ค. ๋‹ค์Œ์œผ๋กœ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ˆ˜ํ–‰ํ•˜๊ธฐ ์ „, 1๋ฒˆ๋ถ€ํ„ฐ ๊ฐ ์ •์ ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” distance ๋ฐฐ์—ด์„ ์—ฐ๊ฒฐ๋œ ๊ฒฝ์šฐ์—๋Š” 0, ์—ฐ๊ฒฐ๋˜์ง€ ์•Š์€ ๊ฒฝ์šฐ์—๋Š” INF๋กœ ์ดˆ๊ธฐํ™”ํ•ด์ฃผ์—ˆ๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ˆ˜ํ–‰ํ•˜๋ฉด์„œ ๊ฐ€์ค‘์น˜๋ฅผ ๋”ํ•ด์ฃผ๋Š” ๋ถ€๋ถ„์€ ๊ฐ ์ขŒํ‘œ๊ฐ„์˜ ๊ฑฐ๋ฆฌ์ด๊ธฐ ๋–„๋ฌธ์— ๋‘ ์  ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ๊ณต์‹์„ ํ†ตํ•ด ๊ตฌํ–ˆ๋‹ค. ์ถ”๊ฐ€์ ์œผ๋กœ ์ธ์ ‘ํ•œ ํ–‰๋ ฌ์—์„œ ์ฐพ๋Š” ์ผ๋ฐ˜์ ์ธ ๊ฒฝ์šฐ์™€ ๋‹ฌ๋ฆฌ ๋ชจ๋“  ๋ฐœ์ „์†Œ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์†ํ•ด์„œ ๊ฐฑ์‹ ํ•ด ์ค„ ํ•„์š”๊ฐ€ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— 1~N๊นŒ์ง€ ์ž๊ธฐ ์ž์‹ ์„ ์ œ์™ธํ•˜๊ณ  ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์‹ ํ•ด์ฃผ์—ˆ๋‹ค. ํ’€.. 2021. 3. 24.
[๋ฐฑ์ค€] 1799. ๋น„์ˆ ๋ฌธ์ œ ํ’€์ด ์ฒ˜์Œ์— ์ƒ๊ฐํ–ˆ๋˜ ๋ฐฉ๋ฒ•์€ ์™„์ „ ํƒ์ƒ‰์„ ํ†ตํ•ด ์ตœ๋Œ€ ์ˆ˜๋ฅผ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์ด์—ˆ๋‹ค. ์ค‘๊ฐ„์— ๊ฐ€์ง€์น˜๊ธฐ๋ฅผ ํ†ตํ•ด ์‹œ๊ฐ„์„ ์ค„์ผ ์ˆ˜ ์žˆ๊ฒ ์ง€๋งŒ n์˜ ์ตœ๋Œ€๊ฐ’์ด 100์ด๊ณ  (๋ชจ๋“  ์ ์— ๋Œ€ํ•ด ๋†“๋Š” ๊ฒฝ์šฐ/ ๋†“์ง€ ์•Š๋Š” ๊ฒฝ์šฐ) * (๋†“์„ ์ˆ˜ ์žˆ๋Š”์ง€ ํŒ๋‹จํ•˜๊ธฐ ์œ„ํ•ด ์–‘ ๋Œ€๊ฐ์„ ์„ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒฝ์šฐ)๋ฅผ ํ•˜๊ฒŒ ๋˜๋ฉด O(2^n * n)์ด๊ธฐ ๋•Œ๋ฌธ์— ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•  ๊ฒƒ ๊ฐ™์•„์„œ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ์ƒ๊ฐํ•ด๋ดค๋‹ค. ์ƒ๊ฐํ•œ ๋ฐฉ๋ฒ•์€ N-Queens์—์„œ ๋ชจ๋“  ํ–‰๋ ฌ์„ ์ €์žฅํ•˜์ง€ ์•Š๊ณ  ํ•ด๋‹น idx์—๋Š” ํ•˜๋‚˜์˜ ๊ฐ’๋งŒ ์˜ฌ ์ˆ˜ ์žˆ๋„๋ก ํ•œ๋‹ค๋ฉด ์‹œ๊ฐ„์„ ์ค„์ผ ์ˆ˜ ์žˆ๋‹ค๋Š” ์ƒ๊ฐ์„ ํ–ˆ๊ณ  ๋ฐ์ดํ„ฐ๋ฅผ ์–ด๋–ป๊ฒŒ ๋ฌถ์–ด์•ผ ํ• ์ง€ ๊ณ ๋ฏผ์„ ํ•ด๋ดค๋‹ค. N-Queens์—์„œ queen์€ ๊ฐ€๋กœ,์„ธ๋กœ๋ฅผ ๊ฐˆ ์ˆ˜ ์žˆ์—ˆ๊ณ  ์ด๋กœ ์ธํ•ด ํ•˜๋‚˜์˜ ํ–‰์— ํ€ธ์„ ๋†“์„ ๊ฒฝ์šฐ์—๋Š” ๊ฐ™์€ ํ–‰์—๋Š” ํ€€์ด ์กด์žฌํ•˜์ง€ ๋ชปํ•˜๋Š” ์„ฑ์งˆ์„ ์ด์šฉํ–ˆ์—ˆ๋‹ค. ์ด.. 2021. 3. 7.
[๋ฐฑ์ค€] 1967. ํŠธ๋ฆฌ์˜ ์ง€๋ฆ„ ๋ฌธ์ œ ํ’€์ด ์ฒ˜์Œ ์‹œ๋„ํ–ˆ๋˜ ๋ฐฉ๋ฒ•์€ 1๋ฒˆ์˜ ์ž์‹๋…ธ๋“œ๋“ค์„ ์‹œ์ž‘์ ์œผ๋กœ ์žก์•„ DFS๋ฅผ ํ†ตํ•ด ํƒ์ƒ‰ํ•˜๋ฉด์„œ ์™ผ์ชฝ ์ž์‹๊ณผ์˜ ๊ฑฐ๋ฆฌ, ์˜ค๋ฅธ์ชฝ ์ž์‹๊ณผ์˜ ๊ฑฐ๋ฆฌ, ๋ถ€๋ชจ์™€์˜ ๊ฑฐ๋ฆฌ ์ค‘์— ์ƒ์œ„ 2๊ฐœ์˜ ๊ฐ’์„ ๊ณจ๋ผ ์ตœ๋Œ€๊ฐ’์„ ๊ฐฑ์‹ ํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ์ง„ํ–‰ํ•˜์˜€๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ทธ ์ตœ๋Œ€๊ฐ’์ด 1๋ฒˆ์˜ ๋‹ค๋ฅธ ์ค„๊ธฐ์™€ ์—ฐ๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š”์ง€(notCompleted), ์•„๋‹ˆ๋ฉด ์ด๋ฏธ ์™„์„ฑ๋œ ์ง€๋ฆ„์ธ์ง€(completed) ํŒ๋ณ„ํ•˜๋Š” flag๋ฅผ ํ†ตํ•ด ์ตœ๋Œ€ ์ง€๋ฆ„์„ ๊ตฌํ•˜๋ ค๊ณ  ํ–ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์ด ์ž˜๋ชป๋œ ์ด์œ ๋Š” ๋จผ์ € ๋ฌธ์ œ์—์„œ ์ด์ง„ ํŠธ๋ฆฌ๋ผ๋Š” ์กฐ๊ฑด์ด ์—†๋Š”๋ฐ ์ด์ง„ํŠธ๋ฆฌ๋ผ๊ณ  ๊ฐ€์ •ํ•˜๊ณ  ํ’€์—ˆ๊ธฐ ๋•Œ๋ฌธ์ด๊ณ , ๋˜ํ•œ ์œ„์˜ ๊ทธ๋ž˜ํ”„์—์„œ 4-7 : 100 / 4-8 : 100์œผ๋กœ ์ˆ˜์ •ํ•œ ๊ฒฝ์šฐ ์™ผ์ชฝ ์ค„๊ธฐ์˜ ์ตœ๋Œ€๊ฐ’์ด 200์ด ๋‚˜์™€์•ผํ•˜๋Š”๋ฐ 4์˜ ๋ถ€๋ชจ๋…ธ๋“œ์ธ 2๊ฐ€ ์ž์‹์ด ํ•˜๋‚˜๋ฐ–์— ์—†๊ธฐ ๋•Œ๋ฌธ์— 200 + 5๋กœ ๊ฐฑ์‹ ๋˜๋Š” ๋ฌธ์ œ.. 2021. 3. 6.