[1026/BOJ/Python] ๋ณด๋ฌผ
๋ฌธ์ ์๋ ์์ ์ ์ํ์ด ํญ์ ํฐ ๊ณจ์นซ๊ฑฐ๋ฆฌ์๋ ๋๋ผ๊ฐ ์์๋ค. ์ด ๋๋ผ์ ๊ตญ์ ๊น์ง๋ฏผ์ ๋ค์๊ณผ ๊ฐ์ ๋ฌธ์ ๋ฅผ ๋ด๊ณ ํฐ ์๊ธ์ ๊ฑธ์๋ค.
๋ฌธ์ ์๋ ์์ ์ ์ํ์ด ํญ์ ํฐ ๊ณจ์นซ๊ฑฐ๋ฆฌ์๋ ๋๋ผ๊ฐ ์์๋ค. ์ด ๋๋ผ์ ๊ตญ์ ๊น์ง๋ฏผ์ ๋ค์๊ณผ ๊ฐ์ ๋ฌธ์ ๋ฅผ ๋ด๊ณ ํฐ ์๊ธ์ ๊ฑธ์๋ค.
๋ฌธ์ ์ ์ข ๋ฐ์ด๋ฌ์ค์ธ ์ ๋ฐ์ด๋ฌ์ค๋ ๋คํธ์ํฌ๋ฅผ ํตํด ์ ํ๋๋ค. ํ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๋ฉด ๊ทธ ์ปดํจํฐ์ ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ชจ๋ ์ปดํจํฐ๋ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
๋ฌธ์ ์ ์๋ฅผ ์ ์ฅํ๋ ์คํ์ ๊ตฌํํ ๋ค์, ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๋ช ๋ น์ ์ฒ๋ฆฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ฌธ์ ๊ทธ๋ํ๋ฅผ DFS๋ก ํ์ํ ๊ฒฐ๊ณผ์ BFS๋ก ํ์ํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋จ, ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ ์ด ์ฌ๋ฌ ๊ฐ์ธ ๊ฒฝ์ฐ์๋ ์ ์ ๋ฒํธ๊ฐ ์์ ๊ฒ์ ๋จผ์ ๋ฐฉ๋ฌธํ๊ณ , ๋ ์ด์ ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ด ์๋ ๊ฒฝ์ฐ ์ข ๋ฃํ๋ค. ์ ์ ๋ฒํธ๋ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง์ด๋ค.