์ด ๊ธ์ AHC 27์ ํ์ด ๋ฐฉ๋ฒ์ ๋ํด ๋ด ์ ๊ทผ์ ์ ๋ฆฌํ ๊ธ์ด๋ค.
ํฌ๊ธฐ๋ถํฐ ํฌ๊ธฐ๋ฅผ ๊ฐ์ง๋ 2์ฐจ์ ๋งต์ด ์๊ณ , ์ด ๋งต ์๋ฅผ ๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์ง๋๊ฐ๋ค. ์์ ์์ ์ถ๋ฐํด์ ์์ ์ผ๋ก ๋์์ค๋ ๊ฒฝ๋ก๋ฅผ ํ๋ ๋ฆฌํดํด์ผํ๊ณ , ์ด ๊ฒฝ๋ก๋ ๊ธฐ๋ณธ์ ์ผ๋ก ์งง์ ์๋ก ์ข๋ค. ๊ทธ๋ ์ง๋ง, ๊ฐ ๊ตฌ์ญ๋ง๋ค ์ฅ์ ๋ฌผ์ด ์กด์ฌํ๋ฉฐ, ๊ตฌ์ญ๋ง๋ค ์ฐ๋ ๊ธฐ๊ฐ ์์ด๋ ์๋๊ฐ ๋ค๋ฅด๊ธฐ ๋๋ฌธ์, ๊ฒฝ๋ก๋ฅผ ์ ๋ง๋ค์ด์ผ ํ๋ค.
์ผ๋จ ๊ธธ์ด ์ path
๋ฅผ ๋ง๋ค์๋ค๊ณ ์น๋ฉด, ํ๋ฒ ๋ก๋ด์ ์ํ์ํจ๋ค. ๊ทธ๋ฌ๊ณ ๋์, ~ ๊ตฌ๊ฐ ๊ฒฝ๋ก ๋ฐฉ๋ฌธ์ ์ํค๋ฉด์, ์ ์ฒด ๋งต์ ๋๋ฌ์ ์ ๋๋ฅผ ํฉํ ๊ฒ์ด ์ค์ฝ์ด๊ฐ ๋๋ค.
dfs
์๊ณ ๋ฆฌ์ฆ์ ํตํด ๊น์ด ์ฐ์ ์ผ๋ก ํ์์์ผ, ์ต๋ํ ๋ฐฉ๋ฌธํ ๊ณณ์ 1๋ฒ๋ง ๋ฐฉ๋ฌธํ๋ ์์ผ๋ก ํด์ ๋ค์ ์์ ์ผ๋ก ๋ณต๊ทํ๋๋ก ํ๋ค.
dfs
๋ ์ฌ๋ฌ ๋ฐฉ๋ฒ์ผ๋ก ๋ฐฉ๋ฌธ์ด ๊ฐ๋ฅํจ์ ์ฐฉ์, score
๋ฅผ ๊ณ์ฐํ ์ ์๋๋ก ๋ก์ง์ ์งฐ๊ณ , ์ฌ๋ฌ dfs
๊ฒฝ๋ก ์ค score
๊ฐ ์ต์๊ฐ ๋๋ ๊ฒฝ๋ก๋ฅผ ๋ฆฌํดํ๋๋ก ํ๋ค.
๋ฑํ ํ๋ฐ ์ ๋ต์ ๋ ์ฌ๋ฆฌ์ง ๋ชปํ๋ค. ์์ญ์ ๋๋ ์ผ ํ๋ค.. ๊น์ง๋ ์๊ฐํ์ง๋ง, ์์ญ์ ๋๋๊ณ ์ด๋ป๊ฒ ๋ฐฉ๋ฌธํ์ง? ์์ ๊ตฌํ์ ์ค์ ๋ก ์ด๋ฃจ์ด๋ด์ง๋ ๋ชปํ์.
๋ค๋ฅธ ํ๊ธฐ๊ธ์ ์ฝ์ด๋ณด๋ ๋น ํ์ ๋ฑ์ ํ์ฉํด์, ์ญ์ ์ฝ๊ฒ ๋๋ฌ์์ง๋ ๊ณณ์ ์ฌ๋ฌ๋ฒ ๋ฐฉ๋ฌธํ๋๋ก ๊ฒฝ๋ก๋ฅผ ์ง๋ ๋ฐฉ๋ฒ์ด ์ฃผํจ. ๋ง์ฝ ์ด๋ ๊ฒ ํ์ํ๋๋ฐ ๋ฏธ๋ฐฉ๋ฌธ ์ง์ญ์ด ์๋ค๋ฉด, ๋์ ๋ฏธ๋ฐฉ๋ฌธ ์ง์ญ์ ๋ถ์ด๋ ๊ฒ์ด ์๋๋ผ ๊ธฐ์กด ๊ฒฝ๋ก๋ฅผ ์ต๋ํ ์์ ํ๋ ๋ฐฉ์์ผ๋ก ๋ฏธ๋ฐฉ๋ฌธ ์ง์ญ์ ๋ฐฉ๋ฌธํ๋๋ก ์กฐ์ํ๋๋ฏ ํ๋ค.