[C++] BOJ : 24444 ๋๋น ์ฐ์ ํ์ 1
ยท
์ฝ๋ฉ/c++
โ
๋ฐฑ์ค 24444: ๋๋น ์ฐ์ ํ์ 1 (BFS)"๋ฉ๋ฆฌ ์ ๊ฐ์, ๊ฐ๊น์ด ๊ฒ๋ถํฐ ์ฐจ๊ทผ์ฐจ๊ทผ. ๋๋น ์ฐ์ ํ์ BFS์
๋๋ค ๐"๐ ๋ฌธ์ ๋งํฌ ๋ฐ๋ก๊ฐ๊ธฐ๐ ๋ฌธ์ ์ค๋ช
๋ฌด๋ฐฉํฅ ๊ทธ๋ํ์์ ๋๋น ์ฐ์ ํ์(BFS) ์ ์ํํ์ฌ๊ฐ ์ ์ ์ ๋ฐฉ๋ฌธ ์์๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ ์
๋๋ค.DFS์ ํ์ ๋ฐฉ์์ด ๋ค๋ฅด๊ธฐ ๋๋ฌธ์, ๊ฐ์ ๊ทธ๋ํ์์๋ ๊ฒฐ๊ณผ๊ฐ ๋ฌ๋ผ์ง ์ ์์ต๋๋ค.๐งพ ์
๋ ฅ ํ์์ ์ ์ N, ๊ฐ์ ์ M, ์์ ์ ์ R๋ค์ M์ค์๋ ๊ฐ์ ์ ๋ณด u v (๋ฌด๋ฐฉํฅ ๊ทธ๋ํ)๐จ ์ถ๋ ฅ ํ์1๋ฒ ์ ์ ๋ถํฐ N๋ฒ ์ ์ ๊น์ง, ๋ฐฉ๋ฌธ ์์๋ฅผ ํ ์ค์ฉ ์ถ๋ ฅํฉ๋๋ค.๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ 0์ ์ถ๋ ฅํฉ๋๋ค.๐ฏ ํต์ฌ ํฌ์ธํธBFS๋ ํ(Queue) ๋ฅผ ์ฌ์ฉํ์ฌ ๊ตฌํํฉ๋๋ค.์ธ์ ์ ์ ์ ์ค๋ฆ์ฐจ์์ผ๋ก ๋ฐฉ๋ฌธํด์ผ ํฉ๋๋ค.๋ฐฉ๋ฌธ ์์๋ฅผ ๊ธฐ๋กํ๋ ๋ฐฐ์ด์ด ํ์ํฉ๋๋ค.๐ป ..