Algorithm/๋ฐฑ์ค
[๋ฐฑ์ค] #2529 ๋ถ๋ฑํธ (Python)
๋ถ๋ฑํธ ๋ฌธ์ ์
๋ ฅ : ๋ถ๋ฑํธ ๋ฌธ์์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์ k( 2 ≤ k ≤ 9)์ k๊ฐ์ ๋ถ๋ฑํธ ๊ธฐํธ ์ถ๋ ฅ : ์ ์๋ ๋ถ๋ฑํธ ๊ด๊ณ๋ฅผ ๋ง์กฑํ๋ k+1 ์๋ฆฌ์ ์ต๋, ์ต์ ์ ์ ๋ถ๋ฑํธ์ ๊ฐฏ์์ ๋ถ๋ฑํธ๊ฐ ์ฃผ์ด์ก์ ๋, ๊ทธ ๋ถ๋ฑํธ์ ๋ง๊ฒ ์ ์์ผ๋ก ๋ค์ด๊ฐ ์ ์๋ ์ซ์(0~9)๊ฐ ์กด์ฌํ๋ค.(๋จ, ๋ชจ๋ ์ซ์๋ ๋ฌ๋ผ์ผ ํ๋ค.) ์ฃผ์ด์ง ๋ชจ๋ ๋ถ๋ฑํธ๋ฅผ ๋ง์กฑํ๋ ์ซ์๋ค์ ์ฐพ๊ณ , ๋ถ๋ฑํธ๋ฅผ ์ ๊ฑฐํ๋ฉด ์ ์ํ๋๊ฐ ๋์ค๋๋ฐ, ๊ทธ๋ค ์ค ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ๋ฐํํด์ผํ๋ค. ์
๋ ฅ 2 ์ถ๋ ฅ 897 021 ์ฉ์ด ์ ๋ฆฌ - ๋ฐฑํธ๋ํน ๋ชจ๋ ๊ฐ๋ฅํ ๊ฒฝ์ฐ์ ์ ์ค์์ ํน์ ํ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ฒฝ์ฐ๋ง ์ดํด๋ณด๋ ๊ฒ ๋ต์ด ๋ ๋งํ์ง ํ๋จํ๊ณ ๊ทธ๋ ์ง ์์ผ๋ฉด ํ์์ ์ค๋จ ์ฃผ๋ก ๋ฌธ์ ํ์ด์์๋ DFS ๋ฑ์ผ๋ก ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ํ๋ ๊ณผ์ ์์, ์กฐ๊ฑด๋ฌธ์ผ..