๋ค์ด๋ฒ ํด๋ก๋ฐ๊ฐ ์ด๋ค ๊ณณ์ด๊ณ ์ด๋ค์ด ๋ฌด์์ ํ๋์ง ์๊ฒ ๋๋ค.
์ฃผ๋ก ์์ฐ์ด ์ฒ๋ฆฌ๊ด๋ จ ์ฐ๊ตฌ๋ฅผ ํ๊ณ ๊ฐ๋ฐํ๋ค.
ํด๋ก๋ฐ ๋จํ๋ ํ๋ ์ฌ๊ณ ์ถ์๋ค.
์ ๊ธฐํ๋ ์ :
๋ค์ด๋ฒ๊ฐ ๊ฐ๊ณ ์๋ ์๋ง์ ํ๊ตญ์ด ๋ฐ์ดํฐ(๋ธ๋ก๊ทธ ๊ธ, ์นดํ ๊ธ, ๊ธฐ์ฌ, ์ง์ IN....)๋ฅผ ํ์ฉํด์ ํ๊ตญ์ด ์์ฐ์ด ์ฒ๋ฆฌ ๊ธฐ์ ํฅ์์ ์ํค๋ ๊ฑธ ๋ณด๊ณ ๋ฐ์ดํฐ๋ฅผ ์์ ํ๊ณ ์๋ ๊ฒ์ด ์ง๊ธ ์๋์ ์ผ๋ง๋ ํฐ ๊ฒฝ์๋ ฅ์ธ์ง ์๊ฒ ๋๋ค.
์์ผ๋ก ์ด๋ฐ ๊ฐ๋ฐ ์ปจํผ๋ฐ์ค๋ฅผ ์์ฃผ ์์ฒญํด์ผ๊ฒ ๋ค.
DFS/BFS์ ๋ํด์ ๋ฐฐ์ ๋ค.
์ค๋์ ๊ฐ๋
์ ๋ฐฐ์ฐ๋๋ผ ๋ฌธ์ ๋ ๋ชป ํ์๋ค.
๊ฐ๋
์ด ๋๋ฌด ์ด๋ ค์์ ์ดํด๋ฅผ ํ๋๋ฐ ๊ฑฐ์ 3์๊ฐ์ด ๊ฑธ๋ ธ๋ค.
๋งค๋ฒ ๋๋ผ๋๊ฑฐ์ง๋ง ํ ์น์
๋ง๋ค ํ์์์ ์๊ฐ์ ์ ํด์ ํด์ผ๊ฒ ๋ค. ์ค๋ ์ด๊ฑฐ ํ๋ค๊ฐ ๋ค๋ฅธ ๊ฒ์ ๊ฑฐ์ ๋ชปํ๊ฒ ๋ผ์ ๊ธฐ๋ถ์ด ์ข ๋ณ๋ก์๋ค.
์ง๊ธ์ ์๋ฌด๋ฆฌ ๋ด๋ ๋ญ์ง ์ ๋ชจ๋ฅด๋๊น ๋ฌธ์ ๋ฅผ ๊ผผ๊ผผํ ์ฝ๊ณ ๋ต์ง ๋ณด๊ณ ์ด๋ ๊ฒ ์ ๊ทผํ๋๊ตฌ๋ ํ๋ ๊ฐ์ ๊ณ์ ์ตํ์ ๋ฌธ์ ๋ ๋ง์ผ๋๊น
๋๋์ :
๊ฐ์ฒด ์ฌ๋ผ์ด์ฑ์ ๋ํด์ ๋ฐฐ์ ๋ค.
ํด๋์ค ์ถ์ํ์ ์ถ์ํ ๋ฉ์๋์ ๋ํด์ ๋ฐฐ์ ๋๋ฐ ์ญ์๋ ์ ์ดํด๊ฐ ๊ฐ์ง๋ฅผ ์์๋ค.
์ค๋ ์๊ธฐ ์ ์ ์ ํ๋ธ ๋ณผ ์๊ฐ์ ๋๊ธํ๊ฒ ๊ฐ์๋ฅผ ํ๋ฒ ๋ ๋ด์ผ๊ฒ ๋ค.
์ ํ๋ธ์ ํผ์ ๊ณต๋ถํ๋ ํ์ด์ฌ ๊ฐ์๊ฐ ์๋๋ฐ ๋ด๊ฐ ๋ณด๋ ๊ฐ์ ๋ณด๊ณ ์ด๊ฑธ๋ก ๊ฐ๋ณ๊ฒ ํ๋ฒ ๋ ๋ณด๋ฉด ์ดํด๊ฐ ์ ๋๋ค.