[C++] BOJ : 24444 ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ 1
ยท
์ฝ”๋”ฉ/c++
โœ… ๋ฐฑ์ค€ 24444: ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ 1 (BFS)"๋ฉ€๋ฆฌ ์•ˆ ๊ฐ€์š”, ๊ฐ€๊นŒ์šด ๊ฒƒ๋ถ€ํ„ฐ ์ฐจ๊ทผ์ฐจ๊ทผ. ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ BFS์ž…๋‹ˆ๋‹ค ๐Ÿ‹"๐Ÿ“Ž ๋ฌธ์ œ ๋งํฌ ๋ฐ”๋กœ๊ฐ€๊ธฐ๐Ÿ“Œ ๋ฌธ์ œ ์„ค๋ช…๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„์—์„œ ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS) ์„ ์ˆ˜ํ–‰ํ•˜์—ฌ๊ฐ ์ •์ ์˜ ๋ฐฉ๋ฌธ ์ˆœ์„œ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.DFS์™€ ํƒ์ƒ‰ ๋ฐฉ์‹์ด ๋‹ค๋ฅด๊ธฐ ๋•Œ๋ฌธ์—, ๊ฐ™์€ ๊ทธ๋ž˜ํ”„์—์„œ๋„ ๊ฒฐ๊ณผ๊ฐ€ ๋‹ฌ๋ผ์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.๐Ÿงพ ์ž…๋ ฅ ํ˜•์‹์ •์  ์ˆ˜ N, ๊ฐ„์„  ์ˆ˜ M, ์‹œ์ž‘ ์ •์  R๋‹ค์Œ M์ค„์—๋Š” ๊ฐ„์„  ์ •๋ณด u v (๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„)๐Ÿ–จ ์ถœ๋ ฅ ํ˜•์‹1๋ฒˆ ์ •์ ๋ถ€ํ„ฐ N๋ฒˆ ์ •์ ๊นŒ์ง€, ๋ฐฉ๋ฌธ ์ˆœ์„œ๋ฅผ ํ•œ ์ค„์”ฉ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์€ 0์„ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.๐ŸŽฏ ํ•ต์‹ฌ ํฌ์ธํŠธBFS๋Š” ํ(Queue) ๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๊ตฌํ˜„ํ•ฉ๋‹ˆ๋‹ค.์ธ์ ‘ ์ •์ ์€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.๋ฐฉ๋ฌธ ์ˆœ์„œ๋ฅผ ๊ธฐ๋กํ•˜๋Š” ๋ฐฐ์—ด์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.๐Ÿ’ป ..