๊ถ๊ทน์ ์ผ๋ก ์ทจ์ ์ด ๋ชฉํ์ธ ๋ถํธ์บ ํ์ด๋ค ๋ณด๋, ์ทจ์ ์์ ์ ๋์ ์ธ ์ค์๋๋ฅผ ์ฐจ์งํ๋ ์ฝ๋ฉ ํ ์คํธ์ ๊ด๋ จ๋ ์์ ๋ ์ปค๋ฆฌํ๋ผ์ ํฌํจ๋์ด ์๋ค. ๋จธ์ ๋ฌ๋๊ณผ๋ ๊ฑฐ๋ฆฌ๊ฐ ์กฐ๊ธ ์์ง๋ง, ์ ๊ตญ๋ฏผ์ด ๊ณตํต์ ์ผ๋ก ํต๊ณผํ๋ ์๋ฅ๊ณผ ๊ฐ์ ๋๋. ์ฝํ ๋ฅผ ์ ๋ด์ผ ์ข์ ๊ณณ์ผ๋ก ๊ฐ ์ ์๋ค..!
๋๋ 3๋ ์ ์ C, C++๋ก queue, stack, tree๋ฑ์ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ง์ ๋ฏ์ด์ ๋ค์ ๋น๋ํ๋ฉฐ ํนํ ํธ๋ฆฌ ๋ถ๋ถ ๋งํผ์ ๊ฑฐ์ '์ ๋ณต'ํ๋ ๊ฒฝํ์ด ์๋ค. ์ดํ ๋ฐ๋ ์ ๋ ํ๋ก๊ทธ๋จ ์ธ์ฃผ ์ผ์ ํ์ ๋์๋ ์๋ฃ๊ตฌ์กฐ๋ ์์ฃผ ๋ค๋ค์๋ค..๋ง 3๋ ์ฌ์ด์ ๊ตฐ๋๋ ๋ค๋ ์ค๊ณ ํ๋ ์ฝํ ์ฉ ์๋ฃ๊ตฌ์กฐ์ ๋ํ ๊ฐ์ ์์๋ค. ๋๋ ์ด๋ฒ ์๊ฐ์ ๋ณต์ตํ๋ฉฐ ์ ์ ์ค๋ ฅ๊น์ง ๋์ด์ฌ๋ฆฌ๋ ๊ฒ ๋ชฉํ.
๋ณธ ๊ณผ์ ์ ๋ ธ์ ํธ ๊ฐ์ฌ๋์ด ์งํํ์ จ๋ค. ์์ฒญ๋ ํ๋ฆฌํฐ์ ์๊ฐํ ์๋ฃ๋ก ํ์ต ์ดํด์ ์๋์ ์ธ ๋์์ ์ฃผ์ จ๋ค. ๋งค์ฐ๋งค์ฐ ๋ง์กฑํ๋ ๊ฐ์์์.
๋ณด์๋ง์ ๋๊ปด์ง๋ ์ง๊ด์ ์ธ ์ดํด..
queue๋ถํฐ ์์ํด์ ์ข
๋ฅ๋ณ ์๊ณ ๋ฆฌ์ฆ์ ๋ํ ์ด๋ก ๋ค์ ๊ณต๋ถํ๊ณ , ๊ทธ ์ด๋ก ์ ์ค์ ๋ฌธ์ ์ ์ ์ฉํด๋ณด๋ ์ค์ตํ๋ ์๊ฐ์ผ๋ก ๊ตฌ์ฑ๋์๋ค. leetcode ์ฌ์ดํธ์ ์๋ ์ค์ ๋ฌธ์ ๋ฅผ ํ์์.
๋, ๊ณต์ ๋ ์ด๋ ต์ง๋ง ๋
ธ์ ํธ ๊ฐ์ฌ๋์ด ์ง์ ๊ณต๋ถํ๊ธฐ ์ข๊ฒ ์ ๋ฆฌํด๋์ ๋
ธ์
ํ์ด์ง๋ ์์๊ธฐ์ ์ค์๊ฐ ๊ฐ์๊ฐ ๋๋์๋ ๋ณต์ตํ๊ธฐ์ ๋งค์ฐ ์ฉ์ดํ๋ค.
๋ ธ์ ํ ํ์ด์ง์ ๋ชจ๋ ์ด๋ํด์ ๊ฐ์ ๋ฌธ์ ๋ณ ์ฝ๋๋ฅผ ์ ๋ก๋ ํ๋๋ฐ, ๋ค๋ฅธ ์ฌ๋์ ์ด๋ป๊ฒ ํ์๋ ๊ณ ๋ฏผํ๋ ํ์ ๋ค์ ์ดํด๋ณผ ์ ์์ด์ ์ด ์ ๋ ์ข์์. ๊ฐ์ด ๊ณต๋ถํ๋ ๋๋์ด ๋ง์ด ๋ค์๋ ๊ฐ์์๋ค.
์ด๊ฑด BFS ๋ฌธ์ ๋ฅผ ํ ๋ ๊ทธ๋ฆผํ์ ์๊ฐ์ ์ ๋ฆฌํ ๊ทธ๋ฆผ์ด๋ค. ์ฝ๋ฉ ํ ์คํธ๋ ๋ณต์กํ ๋ ผ๋ฆฌ๋ฅผ ๋ค๋ฃฐ ๋๋ฉด ๊ทธ๋ฆผํ์ด ํจ๊ปํ๋ค. ์ฒ์ ๋ง์ฃผํ ๋ ์๋ฌด๋ฆฌ ์ด๋ ต๊ณ ๋ณต์กํด๋ณด์ด๋ ๊ตฌ์กฐ๋ ํ๋์ฉ ๊ทธ๋ ค๋๊ฐ๋ค๋ณด๋ฉด ์ด๋์ ์ ๋ณตํ ์ ์๋ค.
์ต๊ทผ๊น์ง ๋จธ์ ๋ฌ๋ ๊ณต๋ถํ๋๋ผ ๋งค์ผ์ ๋ถํ์ ๋๋ฐ, ๋ณต์ตํ๋ ๊ฒ์ผ๋ก๋ ๋งค์ผ์ ์๊ฐ์ด ๋ชจ์๋ฅธ ๊ฒ ๊ฐ๋ค. ๊ทธ์ผ ๊ทธ๋ด๊ฒ ์จ๋ผ์ธ ๊ฐ์๊ฐ ์คํ 7์์ ๋๋๋ ๊ฑธ..
๋๋ถ์ ๊ฐํ๋ฅธ ์ค๋ ฅ ํฅ์์ ๋๋ผ๊ณ ์๋ค. ์ง์ํ๋ ์ด์ ์ค ํ๋์ธ ๋์ ์ฑ์ฅ ๊ฐ๋ฅ์ฑ์ ๋ง ๋ณด๋ ์ค์ด๋ค.
์์ผ๋ก๋ ์ ์ง.