2024/11 29

99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋”” 13์ผ์ฐจ TIL / ๊ทธ๋ฆฌ๋””

โœ๏ธ ๋ฌธ์ œhttps://www.acmicpc.net/problem/27961 ๋งˆ๋ฒ•์†Œ๋…€์ธ ๋งˆ๋„์นด๋Š” ๋„ˆ๋ฌด๋‚˜๋„ ๊ณ ์–‘์ด๋ฅผ ์ข‹์•„ํ•˜๋Š” ๋‚˜๋จธ์ง€ ๋งˆ๋ฒ•์„ ์ด์šฉํ•˜์—ฌ ๊ณ ์–‘์ด N๋งˆ๋ฆฌ๋ฅผ ์ง‘์—์„œ ํ‚ค์šฐ๊ธฐ๋กœ ๊ฒฐ์‹ฌํ–ˆ๋‹ค!๋งˆ๋„์นด๋Š” ํ•œ ๋ฒˆ์˜ ํ–‰๋™์—์„œ ๋‹ค์Œ 2$2$๊ฐ€์ง€ ๋งˆ๋ฒ• ์ค‘ ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•˜์—ฌ ์‚ฌ์šฉํ•œ๋‹ค. ์ฒ˜์Œ์—๋Š” ๋งˆ๋„์นด์˜ ์ง‘์— ๊ณ ์–‘์ด๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค. ์ƒ์„ฑ ๋งˆ๋ฒ•: ๊ณ ์–‘์ด 1๋งˆ๋ฆฌ๋ฅผ ๋งˆ๋„์นด์˜ ์ง‘์— ์ƒ์„ฑํ•œ๋‹ค.๋ณต์ œ ๋งˆ๋ฒ•: ๋งˆ๋„์นด์˜ ์ง‘์— ์žˆ๋Š” ๊ณ ์–‘์ด ์ผ๋ถ€ ๋˜๋Š” ์ „๋ถ€๋ฅผ ๋Œ€์ƒ์œผ๋กœ ํ•˜์—ฌ ๋ณต์ œํ•œ๋‹ค. ์ฆ‰, ๋งŒ์•ฝ ํ˜„์žฌ ๋งˆ๋„์นด์˜ ์ง‘์— ๊ณ ์–‘์ด๊ฐ€ k๋งˆ๋ฆฌ ์กด์žฌํ•œ๋‹ค๋ฉด, 0๋งˆ๋ฆฌ ์ด์ƒ k๋งˆ๋ฆฌ ์ดํ•˜์˜ ๊ณ ์–‘์ด๋ฅผ ๋งˆ๋„์นด์˜ ์ง‘์— ์ถ”๊ฐ€ํ•  ์ˆ˜ ์žˆ๋‹ค. ๋งˆ๋„์นด๋Š” ์œ„์˜ 2๊ฐ€์ง€ ๋งˆ๋ฒ•์„ ์ ์ ˆํžˆ ์‚ฌ์šฉํ•˜์—ฌ, ์ตœ์†Œ์˜ ํ–‰๋™ ํšŸ์ˆ˜๋กœ ๋งˆ๋„์นด์˜ ์ง‘์— ์ •ํ™•ํžˆ N๋งˆ๋ฆฌ์˜ ๊ณ ์–‘์ด๊ฐ€ ์žˆ๋„๋ก ๋งŒ๋“ค๊ณ  ์‹ถ๋‹ค. ๊ณ„์‚ฐ์„..

99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋”” 12์ผ์ฐจ TIL / BFS(๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰)

โœ๏ธ ๋ฌธ์ œhttps://www.acmicpc.net/problem/7569  ์ฒ ์ˆ˜์˜ ํ† ๋งˆํ†  ๋†์žฅ์—์„œ๋Š” ํ† ๋งˆํ† ๋ฅผ ๋ณด๊ด€ํ•˜๋Š” ํฐ ์ฐฝ๊ณ ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ํ† ๋งˆํ† ๋Š” ์•„๋ž˜์˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ๊ฒฉ์ž๋ชจ์–‘ ์ƒ์ž์˜ ์นธ์— ํ•˜๋‚˜์”ฉ ๋„ฃ์€ ๋‹ค์Œ, ์ƒ์ž๋“ค์„ ์ˆ˜์ง์œผ๋กœ ์Œ“์•„ ์˜ฌ๋ ค์„œ ์ฐฝ๊ณ ์— ๋ณด๊ด€ํ•œ๋‹ค. ์ฐฝ๊ณ ์— ๋ณด๊ด€๋˜๋Š” ํ† ๋งˆํ† ๋“ค ์ค‘์—๋Š” ์ž˜ ์ต์€ ๊ฒƒ๋„ ์žˆ์ง€๋งŒ, ์•„์ง ์ต์ง€ ์•Š์€ ํ† ๋งˆํ† ๋“ค๋„ ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ๋ณด๊ด€ ํ›„ ํ•˜๋ฃจ๊ฐ€ ์ง€๋‚˜๋ฉด, ์ต์€ ํ† ๋งˆํ† ๋“ค์˜ ์ธ์ ‘ํ•œ ๊ณณ์— ์žˆ๋Š” ์ต์ง€ ์•Š์€ ํ† ๋งˆํ† ๋“ค์€ ์ต์€ ํ† ๋งˆํ† ์˜ ์˜ํ–ฅ์„ ๋ฐ›์•„ ์ต๊ฒŒ ๋œ๋‹ค. ํ•˜๋‚˜์˜ ํ† ๋งˆํ† ์— ์ธ์ ‘ํ•œ ๊ณณ์€ ์œ„, ์•„๋ž˜, ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ, ์•ž, ๋’ค ์—ฌ์„ฏ ๋ฐฉํ–ฅ์— ์žˆ๋Š” ํ† ๋งˆํ† ๋ฅผ ์˜๋ฏธํ•œ๋‹ค. ๋Œ€๊ฐ์„  ๋ฐฉํ–ฅ์— ์žˆ๋Š” ํ† ๋งˆํ† ๋“ค์—๊ฒŒ๋Š” ์˜ํ–ฅ์„ ์ฃผ์ง€ ๋ชปํ•˜๋ฉฐ, ํ† ๋งˆํ† ๊ฐ€ ํ˜ผ์ž ์ €์ ˆ๋กœ ์ต๋Š” ๊ฒฝ์šฐ๋Š” ์—†๋‹ค๊ณ  ๊ฐ€์ •ํ•œ๋‹ค. ์ฒ ์ˆ˜๋Š” ์ฐฝ๊ณ ์— ๋ณด๊ด€๋œ..

99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋”” 11์ผ์ฐจ TIL / DFS(๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰)

โœ๏ธ ๋ฌธ์ œhttps://www.acmicpc.net/problem/25195  N๊ฐœ์˜ ์ •์ ๊ณผ M๊ฐœ์˜ ๊ฐ„์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ง„, ์‚ฌ์ดํด์ด ์—†๋Š” ๋ฐฉํ–ฅ๊ทธ๋ž˜ํ”„(DAG)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.ํˆฌ์–ด๋ฆฌ์ŠคํŠธ ๊ณฐ๊ณฐ์ด๋Š” ์ข…์ข… ์ด ๊ทธ๋ž˜ํ”„ ์œ„์—์„œ ์—ฌํ–‰์„ ๋– ๋‚œ๋‹ค. ํˆฌ์–ด๋ฆฌ์ŠคํŠธ ๊ณฐ๊ณฐ์ด์˜ ์—ฌํ–‰์€ 1๋ฒˆ ์ •์ ์—์„œ ์ถœ๋ฐœํ•ด ๊ฐ„์„ ์„ ๋”ฐ๋ผ์„œ ์ด๋™ํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋‹ค๊ฐ€ ๋” ์ด์ƒ ๊ฐ„์„ ์„ ๋”ฐ๋ผ์„œ ์ด๋™ํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ ํˆฌ์–ด๋ฆฌ์ŠคํŠธ์˜ ์—ฌํ–‰์€ ์ข…๋ฃŒ๋œ๋‹ค.ํˆฌ์–ด๋ฆฌ์ŠคํŠธ ๊ณฐ๊ณฐ์ด์˜ ์—ด์„ฑ ํŒฌ์ธ ํŒฌํด๋Ÿฝ ๊ณฐ๊ณฐ์ด๋Š” ํˆฌ์–ด๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋‚˜๊ธฐ ์œ„ํ•ด ๊ทธ๋ž˜ํ”„ ์œ„์˜ ์ •์  ์ผ๋ถ€์—์„œ ์ž ๋ณตํ•˜๊ณค ํ•œ๋‹ค. ํŒฌํด๋Ÿฝ ๊ณฐ๊ณฐ์ด๊ฐ€ ์ž ๋ณตํ•œ ์ •์  ์œ„์— ํˆฌ์–ด๋ฆฌ์ŠคํŠธ ๊ณฐ๊ณฐ์ด๊ฐ€ ์„œ ์žˆ๊ฒŒ ๋˜๋ฉด ํˆฌ์–ด๋ฆฌ์ŠคํŠธ ๊ณฐ๊ณฐ์ด์™€ ํŒฌํด๋Ÿฝ ๊ณฐ๊ณฐ์ด๊ฐ€ ๋งŒ๋‚˜๊ฒŒ ๋œ๋‹ค.์˜ค๋Š˜๋„ ํˆฌ์–ด๋ฆฌ์ŠคํŠธ ๊ณฐ๊ณฐ์ด๋Š” ์Œ์•…์„ ๋“ค์œผ๋ฉด์„œ ์—ฌํ–‰์„ ๋– ๋‚˜๋ ค๊ณ  ํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋‹ค๊ฐ€ Twice์˜ ๋…ธ๋ž˜์ธ "YES..

99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋”” 10์ผ์ฐจ TIL / BFS(๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰)

โœ๏ธ ๋ฌธ์ œhttps://www.acmicpc.net/problem/18352 ์–ด๋–ค ๋‚˜๋ผ์—๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€์˜ ๋„์‹œ์™€ M๊ฐœ์˜ ๋‹จ๋ฐฉํ–ฅ ๋„๋กœ๊ฐ€ ์กด์žฌํ•œ๋‹ค. ๋ชจ๋“  ๋„๋กœ์˜ ๊ฑฐ๋ฆฌ๋Š” 1์ด๋‹ค.์ด ๋•Œ ํŠน์ •ํ•œ ๋„์‹œ X๋กœ๋ถ€ํ„ฐ ์ถœ๋ฐœํ•˜์—ฌ ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๋„์‹œ ์ค‘์—์„œ, ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๊ฐ€ ์ •ํ™•ํžˆ K์ธ ๋ชจ๋“  ๋„์‹œ๋“ค์˜ ๋ฒˆํ˜ธ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋˜ํ•œ ์ถœ๋ฐœ ๋„์‹œ X์—์„œ ์ถœ๋ฐœ ๋„์‹œ X๋กœ ๊ฐ€๋Š” ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋Š” ํ•ญ์ƒ 0์ด๋ผ๊ณ  ๊ฐ€์ •ํ•œ๋‹ค.์˜ˆ๋ฅผ ๋“ค์–ด N=4, K=2, X=1์ผ ๋•Œ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ทธ๋ž˜ํ”„๊ฐ€ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž. ์ด ๋•Œ 1๋ฒˆ ๋„์‹œ์—์„œ ์ถœ๋ฐœํ•˜์—ฌ ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š” ๋„์‹œ ์ค‘์—์„œ, ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๊ฐ€ 2์ธ ๋„์‹œ๋Š” 4๋ฒˆ ๋„์‹œ ๋ฟ์ด๋‹ค.  2๋ฒˆ๊ณผ 3๋ฒˆ ๋„์‹œ์˜ ๊ฒฝ์šฐ, ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๊ฐ€ 1์ด๊ธฐ ๋•Œ๋ฌธ์— ์ถœ๋ ฅํ•˜์ง€ ์•Š๋Š”๋‹ค. ๐Ÿค– ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ ๐Ÿง ๋‚œ์ด๋„/์†Œ์š”..

99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋”” 9์ผ์ฐจ TIL / BFS(๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰)

โœ๏ธ ๋ฌธ์ œhttps://www.acmicpc.net/problem/7562  ์ฒด์ŠคํŒ ์œ„์— ํ•œ ๋‚˜์ดํŠธ๊ฐ€ ๋†“์—ฌ์ ธ ์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ํ•œ ๋ฒˆ์— ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์€ ์•„๋ž˜ ๊ทธ๋ฆผ์— ๋‚˜์™€์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นธ์ด ์ฃผ์–ด์ง„๋‹ค. ๋‚˜์ดํŠธ๋Š” ๋ช‡ ๋ฒˆ ์›€์ง์ด๋ฉด ์ด ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์„๊นŒ?  ๐Ÿค– ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ ๐Ÿง ๋‚œ์ด๋„/์†Œ์š” ์‹œ๊ฐ„โœ… ๋‚œ์ด๋„: solved.ac ๊ธฐ์ค€ S1โœ… ์†Œ์š” ์‹œ๊ฐ„: 28๋ถ„ 44์ดˆโœ… ๊ถŒ์žฅ ์‹œ๊ฐ„: 1์‹œ๊ฐ„ ๐Ÿ’ก ํ’€์ด1) ๋ฌธ์ œ ์œ ํ˜• ํŒŒ์•…๋ฌธ์ œ์— ์ฃผ์–ด์ง„ ๊ทธ๋ฆผ๊ณผ ์ตœ์†Œ ์ด๋™ ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ๊ฑธ ๋ณด๊ณ  BFS๋กœ ํ’€์–ด์•ผ๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค. 2) ์•„์ด๋””์–ด ํ๋ฆ„โ‘  ๋‚˜์ดํŠธ๊ฐ€ ์›€์ง์ผ ์ˆ˜ ์žˆ๋Š” ๋ฐฉํ–ฅ ํ‘œํ˜„์ง€๊ธˆ๊นŒ์ง€ ๋ณธ BFS ๋ฌธ์ œ๋“ค์€ ํ•ญ์ƒ ๋ญ”๊ฐ€๋ฅผ 2์ฐจ์› ๋ฆฌ์ŠคํŠธ ์œ„์—์„œ ์›€์ง์—ฌ ๋‹ต์„ ์ฐพ๋Š” ๋ฐฉ์‹์ด์—ˆ๋‹ค. ์ด ๋ฌธ์ œ๋„ ๊ทธ ํ‹€์—์„œ ๋ฒ—์–ด๋‚˜์ง„ ์•Š์ง€..

99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋”” 8์ผ์ฐจ TIL / DFS(๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰)

โœ๏ธ ๋ฌธ์ œhttps://www.acmicpc.net/problem/2644 ์šฐ๋ฆฌ ๋‚˜๋ผ๋Š” ๊ฐ€์กฑ ํ˜น์€ ์นœ์ฒ™๋“ค ์‚ฌ์ด์˜ ๊ด€๊ณ„๋ฅผ ์ดŒ์ˆ˜๋ผ๋Š” ๋‹จ์œ„๋กœ ํ‘œํ˜„ํ•˜๋Š” ๋…ํŠนํ•œ ๋ฌธํ™”๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ์ด๋Ÿฌํ•œ ์ดŒ์ˆ˜๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ๊ณ„์‚ฐ๋œ๋‹ค. ๊ธฐ๋ณธ์ ์œผ๋กœ ๋ถ€๋ชจ์™€ ์ž์‹ ์‚ฌ์ด๋ฅผ 1์ดŒ์œผ๋กœ ์ •์˜ํ•˜๊ณ  ์ด๋กœ๋ถ€ํ„ฐ ์‚ฌ๋žŒ๋“ค ๊ฐ„์˜ ์ดŒ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด ๋‚˜์™€ ์•„๋ฒ„์ง€, ์•„๋ฒ„์ง€์™€ ํ• ์•„๋ฒ„์ง€๋Š” ๊ฐ๊ฐ 1์ดŒ์œผ๋กœ ๋‚˜์™€ ํ• ์•„๋ฒ„์ง€๋Š” 2์ดŒ์ด ๋˜๊ณ , ์•„๋ฒ„์ง€ ํ˜•์ œ๋“ค๊ณผ ํ• ์•„๋ฒ„์ง€๋Š” 1์ดŒ, ๋‚˜์™€ ์•„๋ฒ„์ง€ ํ˜•์ œ๋“ค๊ณผ๋Š” 3์ดŒ์ด ๋œ๋‹ค.์—ฌ๋Ÿฌ ์‚ฌ๋žŒ๋“ค์— ๋Œ€ํ•œ ๋ถ€๋ชจ ์ž์‹๋“ค ๊ฐ„์˜ ๊ด€๊ณ„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฃผ์–ด์ง„ ๋‘ ์‚ฌ๋žŒ์˜ ์ดŒ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๐Ÿค– ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ ๐Ÿง ๋‚œ์ด๋„/์†Œ์š” ์‹œ๊ฐ„โœ… ๋‚œ์ด๋„: solved.ac ๊ธฐ์ค€ S2โœ… ์†Œ์š” ์‹œ๊ฐ„: ์˜ˆ์ „์— ํ’€์—ˆ๋˜ ๋ฌธ์ œ๋ผ ์ธก์ • Xโœ… ๊ถŒ..

99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋”” 7์ผ์ฐจ TIL / ์™„์ „ํƒ์ƒ‰

โœ๏ธ ๋ฌธ์ œhttps://school.programmers.co.kr/learn/courses/30/lessons/84512 ์‚ฌ์ „์— ์•ŒํŒŒ๋ฒณ ๋ชจ์Œ 'A', 'E', 'I', 'O', 'U'๋งŒ์„ ์‚ฌ์šฉํ•˜์—ฌ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š”, ๊ธธ์ด 5 ์ดํ•˜์˜ ๋ชจ๋“  ๋‹จ์–ด๊ฐ€ ์ˆ˜๋ก๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ์‚ฌ์ „์—์„œ ์ฒซ ๋ฒˆ์งธ ๋‹จ์–ด๋Š” "A"์ด๊ณ , ๊ทธ๋‹ค์Œ์€ "AA"์ด๋ฉฐ, ๋งˆ์ง€๋ง‰ ๋‹จ์–ด๋Š” "UUUUU"์ž…๋‹ˆ๋‹ค. ๋‹จ์–ด ํ•˜๋‚˜ word๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ด ๋‹จ์–ด๊ฐ€ ์‚ฌ์ „์—์„œ ๋ช‡ ๋ฒˆ์งธ ๋‹จ์–ด์ธ์ง€ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”. ์ œํ•œ์‚ฌํ•ญword์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 5 ์ดํ•˜์ž…๋‹ˆ๋‹ค.word๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž 'A', 'E', 'I', 'O', 'U'๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. ๐Ÿค– ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ ๐Ÿง ๋‚œ์ด๋„/์†Œ์š” ์‹œ๊ฐ„โœ… ๋‚œ์ด๋„: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค Level..

99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋”” 6์ผ์ฐจ TIL / ์ด๋ถ„ ํƒ์ƒ‰

โœ๏ธ ๋ฌธ์ œhttps://www.acmicpc.net/problem/2805 ์ƒ๊ทผ์ด๋Š” ๋‚˜๋ฌด M๋ฏธํ„ฐ๊ฐ€ ํ•„์š”ํ•˜๋‹ค. ๊ทผ์ฒ˜์— ๋‚˜๋ฌด๋ฅผ ๊ตฌ์ž…ํ•  ๊ณณ์ด ๋ชจ๋‘ ๋งํ•ด๋ฒ„๋ ธ๊ธฐ ๋•Œ๋ฌธ์—, ์ •๋ถ€์— ๋ฒŒ๋ชฉ ํ—ˆ๊ฐ€๋ฅผ ์š”์ฒญํ–ˆ๋‹ค. ์ •๋ถ€๋Š” ์ƒ๊ทผ์ด๋„ค ์ง‘ ๊ทผ์ฒ˜์˜ ๋‚˜๋ฌด ํ•œ ์ค„์— ๋Œ€ํ•œ ๋ฒŒ๋ชฉ ํ—ˆ๊ฐ€๋ฅผ ๋‚ด์ฃผ์—ˆ๊ณ , ์ƒ๊ทผ์ด๋Š” ์ƒˆ๋กœ ๊ตฌ์ž…ํ•œ ๋ชฉ์žฌ์ ˆ๋‹จ๊ธฐ๋ฅผ ์ด์šฉํ•ด์„œ ๋‚˜๋ฌด๋ฅผ ๊ตฌํ•  ๊ฒƒ์ด๋‹ค.๋ชฉ์žฌ์ ˆ๋‹จ๊ธฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋™์ž‘ํ•œ๋‹ค. ๋จผ์ €, ์ƒ๊ทผ์ด๋Š” ์ ˆ๋‹จ๊ธฐ์— ๋†’์ด H๋ฅผ ์ง€์ •ํ•ด์•ผ ํ•œ๋‹ค. ๋†’์ด๋ฅผ ์ง€์ •ํ•˜๋ฉด ํ†ฑ๋‚ ์ด ๋•…์œผ๋กœ๋ถ€ํ„ฐ H๋ฏธํ„ฐ ์œ„๋กœ ์˜ฌ๋ผ๊ฐ„๋‹ค. ๊ทธ ๋‹ค์Œ, ํ•œ ์ค„์— ์—ฐ์†ํ•ด์žˆ๋Š” ๋‚˜๋ฌด๋ฅผ ๋ชจ๋‘ ์ ˆ๋‹จํ•ด๋ฒ„๋ฆฐ๋‹ค. ๋”ฐ๋ผ์„œ, ๋†’์ด๊ฐ€ H๋ณด๋‹ค ํฐ ๋‚˜๋ฌด๋Š” H ์œ„์˜ ๋ถ€๋ถ„์ด ์ž˜๋ฆด ๊ฒƒ์ด๊ณ , ๋‚ฎ์€ ๋‚˜๋ฌด๋Š” ์ž˜๋ฆฌ์ง€ ์•Š์„ ๊ฒƒ์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ํ•œ ์ค„์— ์—ฐ์†ํ•ด์žˆ๋Š” ๋‚˜๋ฌด์˜ ๋†’์ด๊ฐ€ 20, 15, 10, 17์ด๋ผ๊ณ  ํ•˜์ž. ์ƒ..

99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋”” 5์ผ์ฐจ TIL / BFS(๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰)

โœ๏ธ ๋ฌธ์ œhttps://www.acmicpc.net/problem/24444 ์˜ค๋Š˜๋„ ์„œ์ค€์ด๋Š” ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS) ์ˆ˜์—… ์กฐ๊ต๋ฅผ ํ•˜๊ณ  ์žˆ๋‹ค. ์•„๋น ๊ฐ€ ์ˆ˜์—…ํ•œ ๋‚ด์šฉ์„ ํ•™์ƒ๋“ค์ด ์ž˜ ์ดํ•ดํ–ˆ๋Š”์ง€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด์„œ ํ™•์ธํ•ด๋ณด์ž.N๊ฐœ์˜ ์ •์ ๊ณผ M๊ฐœ์˜ ๊ฐ„์„ ์œผ๋กœ ๊ตฌ์„ฑ๋œ ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(undirected graph)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ •์  ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ์ด๊ณ  ๋ชจ๋“  ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜๋Š” 1์ด๋‹ค. ์ •์  R์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์œผ๋กœ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•  ๊ฒฝ์šฐ ๋…ธ๋“œ์˜ ๋ฐฉ๋ฌธ ์ˆœ์„œ๋ฅผ ์ถœ๋ ฅํ•˜์ž.๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ ์˜์‚ฌ ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ์ธ์ ‘ ์ •์ ์€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•œ๋‹ค. ๐Ÿค– ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ ๐Ÿง ๋‚œ์ด๋„/์†Œ์š” ์‹œ๊ฐ„โœ… ๋‚œ์ด๋„: solved.ac ๊ธฐ์ค€ S2โœ… ์†Œ์š” ์‹œ๊ฐ„: 20๋ถ„โœ… ๊ถŒ์žฅ ์‹œ๊ฐ„: 45๋ถ„ ๐Ÿ’ก ํ’€์ด1) ๋ฌธ์ œ ์œ ํ˜• ํŒŒ์•…4์ผ์ฐจ ๋ฌธ์ œ์™€ ์œ ์‚ฌํ•œ ..