๋ฐฑ์ค€ ๋ถˆ! 1

๋ฐฑ์ค€ 4179๋ฒˆ ๋ถˆ!

๋ฌธ์ œ ๋ณด๋Ÿฌ๊ฐ€๊ธฐ : https://www.acmicpc.net/problem/4179 4179๋ฒˆ: ๋ถˆ! ์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋œ ๋‘ ์ •์ˆ˜ R๊ณผ C๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹จ, 1 ≤ R, C ≤ 1000 ์ด๋‹ค. R์€ ๋ฏธ๋กœ ํ–‰์˜ ๊ฐœ์ˆ˜, C๋Š” ์—ด์˜ ๊ฐœ์ˆ˜์ด๋‹ค. ๋‹ค์Œ ์ž…๋ ฅ์œผ๋กœ R์ค„๋™์•ˆ ๊ฐ๊ฐ์˜ ๋ฏธ๋กœ ํ–‰์ด ์ฃผ์–ด์ง„๋‹ค. ๊ฐ๊ฐ์˜ ๋ฌธ www.acmicpc.net ์ด๋ฒˆ ๋ฌธ์ œ๋Š” ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS) ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค. ์‹œ์ž‘์ ์ด ๋‘ ์ข…๋ฅ˜์ด๋ฏ€๋กœ ๋ถˆ์„ ์œ„ํ•œ bfs, ์ง€ํ›ˆ์ด๋ฅผ ์œ„ํ•œ bfs๋ฅผ ๊ฐ๊ฐ ๋Œ๋ ค์•ผํ•ฉ๋‹ˆ๋‹ค. [ํ•„์š”ํ•œ ๊ฒƒ] 1. ๋ถˆ์˜ ์ „ํŒŒ ์‹œ๊ฐ„์„ ๊ธฐ๋กํ•  ๋ฐฐ์—ด dist1 (-1๋กœ ์ดˆ๊ธฐํ™”) 2. ์ง€ํ›ˆ์ด์˜ ํƒˆ์ถœ ์‹œ๊ฐ„์„ ๊ธฐ๋กํ•  ๋ฐฐ์—ด dist2 (-1๋กœ ์ดˆ๊ธฐํ™”) 3. ๋ถˆ์˜ bfs๋ฅผ ์œ„ํ•œ ํ q1 4. ์ง€ํ›ˆ์ด์˜ bfs๋ฅผ ์œ„ํ•œ ํ q2 ใ€Š๋ฌธ์ œ ํ’€์ด..

๋ฐ˜์‘ํ˜•