๋ชฉ๋กํ•ญ์ฒด ์ธ์‹ (1)

Hello Ocean! ๐ŸŒผ

[C++/๋ฐฑ์ค€] 22352. ํ•ญ์ฒด ์ธ์‹

๋ฌธ์ œ https://www.acmicpc.net/problem/22352 22352๋ฒˆ: ํ•ญ์ฒด ์ธ์‹ ์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” SP ์ดฌ์˜ ๊ฒฐ๊ณผ์˜ ํฌ๊ธฐ๋ฅผ ์˜๋ฏธํ•˜๋Š” ๋‘ ์ •์ˆ˜ $N$๊ณผ $M$์ด ์ฃผ์–ด์ง„๋‹ค. ($1 \le N, M \le 30$) ์ด๋Š” ์ดฌ์˜ ๊ฒฐ๊ณผ๊ฐ€ ์„ธ๋กœ๋กœ $N$์นธ, ๊ฐ€๋กœ๋กœ $M$์นธ ํฌ๊ธฐ์˜ ๊ฒฉ์ž๋ผ๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค. ๋‹ค์Œ $N$๊ฐœ์˜ ์ค„์—๋Š” www.acmicpc.net ํ’€์ด ๋‘ ๋ฐฐ์—ด(before์™€ after)์„ (0, 0)๋ถ€ํ„ฐ ํ•œ ์นธ์”ฉ ๋น„๊ตํ•˜๋ฉด์„œ, ๊ฐ’์ด ๋‹ค๋ฅผ ๋•Œ BFS๋ฅผ ์‹คํ–‰ํ•ด์„œ before๋ฐฐ์—ด์˜ ๊ฐ’์„ after๋ฐฐ์—ด์˜ ๊ฐ’์œผ๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค. ์ด๋ ‡๊ฒŒ BFS๋ฅผ ๋Œ๋ฆฌ๊ณ  ๋‚˜์„œ๋„ ๋‘ ๋ฐฐ์—ด์— ๊ฐ’์ด ๋‹ค๋ฅธ ์นธ์ด ์žˆ๋‹ค๋ฉด, NO์ด๊ณ  ์•„๋‹ˆ๋ฉด YES์ด๋‹ค. ์—ฌ๊ธฐ์„œ ์ฃผ์˜ํ•ด์•ผ ํ•  ์ ์€, BFS๋ฅผ "๋”ฑ ํ•œ ๋ฒˆ" ๋Œ๋ ค์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ์•„๋ž˜ ์˜ˆ์‹œ๋ฅผ ..
Algorithm 2021. 9. 14. 20:26
์ด์ „ Prev 1 Next ๋‹ค์Œ