๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก๊นŠ์ด์šฐ์„ ํƒ์ƒ‰ (2)

CS Student’s SAP&Tech Journey๐Ÿ’ซ

[ํŒŒ์ด์ฌ] 24479๋ฒˆ: ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰1 / ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰ DFS

1. ๋ฐฑ์ค€ 24479๋ฒˆ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—… - ๊นŠ์ด ์šฐ์„ ํƒ์ƒ‰ 1 [๋ฐฑ์ค€] 24479๋ฒˆ : ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—… - ๊นŠ์ด ์šฐ์„ ํƒ์ƒ‰ 2. ์˜ค๋Š˜์˜ ํšŒ๊ณ  0. ๋ฌธ์ œ ๋ถ„์„N๊ฐœ์˜ ์ •์ ๊ณผ M๊ฐœ์˜ ๊ฐ„์„ ์œผ๋กœ ๊ตฌ์„ฑ๋œ ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(undirected graph)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ •์  ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ์ด๊ณ  ๋ชจ๋“  ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜๋Š” 1์ด๋‹ค. ์ •์  R์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์œผ๋กœ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•  ๊ฒฝ์šฐ ๋…ธ๋“œ์˜ ๋ฐฉ๋ฌธ ์ˆœ์„œ๋ฅผ ์ถœ๋ ฅํ•˜์ž.๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ ์˜์‚ฌ ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ์ธ์ ‘ ์ •์ ์€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•œ๋‹ค. : ์ธ์ ‘ ์ •์ ์€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธ์‹œ์ผœ์•ผํ•˜๋ฏ€๋กœ ์ •๋ ฌ์„ ํ•ด์ฃผ์–ด์•ผ ํ•œ๋‹ค. 1. ์ž…๋ ฅ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ์ˆ˜ N (5 ≤ N ≤ 100,000), ๊ฐ„์„ ์˜ ์ˆ˜ M (1 ≤ M ≤ 200,000), ์‹œ์ž‘ ์ •์  R (1 ≤ R ≤ N)์ด ์ฃผ์–ด์ง„๋‹ค.๋‹ค์Œ M..

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰(DFS)์ด๋ž€

1. ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ DFS ( Depth - First Search) DFS๋Š” ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์ด๋ผ๊ณ ๋„ ๋ถ€๋ฅด๋ฉฐ ๊ทธ๋ž˜ํ”„์—์„œ ๊นŠ์€ ๋ถ€๋ถ„์„ ์šฐ์„ ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. DFS๋Š” ์Šคํƒ ์ž๋ฃŒ๊ตฌ์กฐ ํ˜น์€ ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜๋ฉฐ, ๊ตฌ์ฒด์ ์ธ ๋™์ž‘ ๊ณผ์ •์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.ํƒ์ƒ‰ ์‹œ์ž‘ ๋…ธ๋“œ๋ฅผ ์Šคํƒ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ๋ฅผ ํ•ฉ๋‹ˆ๋‹ค.์Šคํƒ์˜ ์ตœ์ƒ๋‹จ ๋…ธ๋“œ์— ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๊ฐ€ ํ•˜๋‚˜๋ผ๋„ ์žˆ์œผ๋ฉด ๊ทธ ๋…ธ๋“œ๋ฅผ ์Šคํƒ์— ๋„ฃ๊ณ  ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•ฉ๋‹ˆ๋‹ค. ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด ์Šคํƒ์—์„œ ์ตœ์ƒ๋‹จ ๋…ธ๋“œ๋ฅผ ๊บผ๋ƒ…๋‹ˆ๋‹ค.๋”์ด์ƒ 2๋ฒˆ์˜ ๊ณผ์ •์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค. 2. DFS ๋™์ž‘ ์˜ˆ์‹œ (์˜ˆ์‹œ๋Š” ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ์ธ์ ‘ ๋…ธ๋“œ ๋ถ€ํ„ฐ ๋ฐฉ๋ฌธ)[step 0] ๊ทธ๋ž˜ํ”„ ์ค€๋น„ (๋ฐฉ๋ฌธ ๊ธฐ์ค€ : ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ์ธ์ ‘๋…ธ๋“œ๋ถ€ํ„ฐ) / ์‹œ์ž‘๋…ธ๋“œ : 1[step 1..