(Challenge)BFS Special Judge
2ํ์ฐจ ํ์ด ํ๋ฆฐ ์ด์
bfs ์์ ์ ๋ ฅ๋ฐ์ ๋ 1์ ๋นผ์ฃผ์ง ์์์ ํ์ ๋ฃ๊ณ ๋บ ๊ฑด(x) 0์ธ๋ฐ, order[0] = 1, x = 0์ผ๋ก ๊ฐ์ง ์๊ธฐ ๋๋ฌธ์ 0์ด๋ผ๋ ์ค๋ต์ ์ถ๋ ฅํ๋ค.(์ฌ์ค์ ์ ๋๋ก ์ ์คํ๋ ๊ฒ์)
ํ๊ฐ ๋น์์ ๋ 0์ ์ถ๋ ฅํ๊ณ ํ๋ก๊ทธ๋จ์ ์ข ๋ฃํด์ผํ๋ค.? ํ๊ฐ ๋น์์ผ๋ฉด ํ๋ก๊ทธ๋จ์ ์ข ๋ฃํ๋ ๊ฒ๊น์ง ์๊ฒ ๋๋ฐ ์ 0์ ์ถ๋ ฅํ๋?
๋ฌธ์ ์ ํต์ฌ
order์ ์์๊ฐ x์ ์ธ์ ๋ ธ๋์ธ์ง ํ์ธํ๋ ๊ฒ์ ๊ตฌํํ๋ ๊ฒ์ด๋ค! x์ ์ธ์ ๋ ธ๋๋ฅผ ๋ฐ๋ก ํ์ ๋ฃ๋ ๊ฒ ์๋๋ผ, ์ธ์ ๋ ธ๋๋ค์ parent๋ผ๋ ๋ฐฐ์ด์ ์ ์ฅํ๊ณ , ์ธ์ ๋ ธ๋ ๊ฐฏ์๋ฅผ ์ธ์ค๋ค. ์๋ฅผ ๋ค์ด x=0, x์ ์ธ์ ๋ ธ๋๊ฐ 1,2 2๊ฐ์ผ ๋ parent[0]=1,parent[0]=2๋ ์ ๋์ง๋ง, parent[1]=0,parent[2]=0 ์ ๊ฐ๋ฅํ๊ธฐ ๋๋ฌธ์ x์ ์ธ์ ๋ ธ๋๋ฅผ ์ธ๋ฑ์ค๋ก ํ๋ parent ๋ฐฐ์ด์ ๊ฐ์ผ๋ก x๋ฅผ ๋ฃ์ด์ค๋ค!
์ธ์ ๋ ธ๋ ๊ฐฏ์๋งํผ order ๋ฐฐ์ด ๊ฐ๋ค์ ํ์ ๋ฃ์ด์ค๋ค! ๋จ, ํ์ ๋ฃ์ ๋, parent[order ๋ฐฐ์ด ๊ฐ]์ด x์ธ์ง(x์ ์ธ์ ๋ ธ๋์ธ์ง) ํ์ธํ๊ณ ๋ฃ์ด์ค๋ค! ๋ง์ผ๋ฉด ํ์ ๋ฃ๊ณ , ์๋๋ฉด ์์๊ฐ ํ๋ฆฐ ๊ฒ์ด๋ฏ๋ก 0์ ์ถ๋ ฅํ๊ณ ํ๋ก๊ทธ๋จ ์ข ๋ฃ!
m์ด ์กด์ฌํ๋ ์ด์ , ์๋ฏธ
m์ 1์์ ์์ํ๋ค. ๋จ์ํ ํ์ ํฌ๊ธฐ๋ฅผ ์๋ฏธํ๋ ๊ฒ์ด ์๋๋ผ ํ์ ๋ฃ์ ์, order ๋ฐฐ์ด์ ์ธ๋ฑ์ค๊ฐ ๋๋ค! ์๋ํ๋ฉด order[0]์์ ์์ํ๊ณ , ์ด๊ฒ์ ์ธ์ ๋ ธ๋๋ order[1]๋ถํฐ cnt(์ธ์ ๋ ธ๋ ๊ฐฏ์)๋งํผ์ด๊ธฐ ๋๋ฌธ์ 1(m)๋ถํฐ cnt๋งํผ ํ์ ๋ฃ๊ณ ! m=1-> m+cnt=3 ์ผ๋ก ์ ๋ฐ์ดํธํด์ค๋ค! m=3์ ์๋ฏธ๋ ๊ทธ ๋ค์ ์ ์ ์ ์ธ์ ๋ ธ๋ ์ถ๊ฐ๋ order[3]๋ถํฐ cnt๋งํผ ์ถ๊ฐํ๋ค๋ ๊ฒ์ด๋ค!
Last updated
Was this helpful?