๋ฌธ์ ์ ๊ทผ
https://school.programmers.co.kr/learn/courses/30/lessons/92345
ํ๋ก๊ทธ๋๋จธ์ค
SW๊ฐ๋ฐ์๋ฅผ ์ํ ํ๊ฐ, ๊ต์ก์ Total Solution์ ์ ๊ณตํ๋ ๊ฐ๋ฐ์ ์ฑ์ฅ์ ์ํ ๋ฒ ์ด์ค์บ ํ
programmers.co.kr
์ด๊ธธ ์ ์๋ ๊ฒฝ์ฐ ์ต์์ ํด์ผ๋ก ์ด๊ธฐ๋ ๋ฐฉํฅ์ผ๋ก ๊ฐ๊ณ ์ด๊ธธ ์ ์๋ ๊ฒฝ์ฐ ์ต๋ํ ์ค๋ ๋ฒํธ ์ ์๊ฒ ํ๋ผ๋๊ฒ ์ดํด๊ฐ ์๋์ ์ ๋ง ์ด๋ ค์ ๋ ๋ฌธ์ ์๋ค.
์ด๋ฐ ๊ฒฝ์ฐ๋ฅผ ๋ฏธ๋๋งฅ์ค ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๊ณ ํ๋ค๋๋ฐ ์ด๋ฐ ๊ตฌ์ฒด์ ์ธ ์ ๋ณด์์ด๋ 5x5 boardํ์ด๋ฏ๋ก ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ํด๋ณธ๋ค๋ ์๊ฐ์ ๊ฐ๊ณ ์ ๊ทผํ๋ค๋ฉด ๋๊ฐ์ด ํ ์ ์๋ค.
๋ฌธ์ ํ์ด
์ํ์ข์ฐ๋ก ์์ง์ผ ์ ์๊ณ map์ ๋ฒ์ด๋ ์ ์์ผ๋ฉฐ ๋ฐํ์ด ์๋ ๊ณณ์ผ๋ก๋ง ์ด๋ํ ์ ์๋ค๋ ๋ด์ฉ์ ๋ณด์๋ง์ ๊ฐ์ฅ ๋จผ์ ๋ฐฉํฅ ๋ฒกํฐ์ map์ ๋ฒ์ด๋๋ ๊ฒฝ์ฐ + ๋ฐํ์ด ์๋์ง๋ฅผ ํ์ธํด์ ํด๋น ๊ณต๊ฐ์ผ๋ก ์ด๋ํ ์ ์๋์ง์ ์ฌ๋ถ๋ฅผ ๋ฐํํด์ฃผ๋ isRange ํจ์๋ฅผ ๋ง๋ค์ด์คฌ๋ค.
๊ทธ ํ dfs๋ฅผ ํตํด ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ํ๋๋ฐ ๋ฐํ๊ฐ์ ๊ฒฝ์ฐ int๋ฐฐ์ด์ ์ฌ์ฉํด์ {์น๋ฆฌ ์ฌ๋ถ(0์ด๋ฉด ์น๋ฆฌ, 1์ด๋ฉด ํจ๋ฐฐ), ํด ์}๋ก ์ฌ์ฉํ๋ค.
๊ทธ๋ฆฌ๊ณ A๋ถํฐ ์ด๋์ ์์ํด์ A, B, A, B, ... ์์๋ก ๋ฒ๊ฐ์๊ฐ๋ฉฐ ์ด๋์ ํ๊ธฐ ๋๋ฌธ์ ์ด๋ฅผ ํ๋์ ์ฌ๊ท์์ ๋ํ๋ด๊ธฐ ์ํด opponent์ me ๋ผ๋ int[]๋ฅผ ํตํด A์ B์ ํ์ฌ ์์น๋ฅผ ์ ๋ฌํด์ฃผ์๋ค.
์ฐ์ ํ์ฌ ๋ฐํ์ด ์ฌ๋ผ์ง๋ค๋ฉด(๊ฐ์ ์์น์ ์๋ค ๋๊ตฐ๊ฐ ๋จผ์ ์ด๋ํ๋ค๋ฉด ๋ฐํ์ด ์ฌ๋ผ์ง๋ฏ๋ก) ์ด๋ํ์ง๋ชปํ๊ณ ํจ๋ฐฐํ๋ฏ๋ก ํจ๋ฐฐ๋ฅผ ๋ํ๋ด๋ 1๊ณผ ์ด๋ํ์ง ๋ชปํ์ผ๋ฏ๋ก ํด์ 0 ์ ๋ฐฐ์ด์ ๋ด์ {1, 0}์ return ํ๋ค.
๊ทธ๋ฆฌ๊ณ ํ์ฌ ํ๋ ์ด์ด๊ฐ ์ด๊ธฐ๋ ๊ฒฝ์ฐ๊ฐ ์๋ค๋ฉด ๊ฐ์ฅ ์ต์ํ์ ํด์ผ๋ก ์น๋ฆฌํด์ผํ๋ฏ๋ก winTurn๋ณ์๋ฅผ 26์ผ๋ก ์ด๊ธฐํํ์๊ณ (์ต๋ 5 * 5 ๋ฐฐ์ด์ด๋ฏ๋ก 25 ์ด์์ผ๋ก๋ ํด์ด ์กด์ฌํ ์ ์์) ๋ฌด์กฐ๊ฑด ํจ๋ฐฐํ๋ค๋ฉด ๊ฐ์ฅ ์ค๋ ํด์ผ๋ก ๋ฒํ จ์ผํ๋ฏ๋ก loseTurn์ 0์ผ๋ก ์ด๊ธฐํํ์๋ค.
๋ํ, ํ์ฌ ํ๋ ์ด์ด๊ฐ ์ด๋ป๊ฒ๋ ์ด๊ธธ ์ ์๋์ง๋ฅผ ๋ํ๋ด๋ canWin๊ณผ ์ํ์ข์ฐ ์ด๋๋ก๋ ์ด๋ํ ์ ์๋์ง๋ฅผ ๋ํ๋ด๋ canMove๋ฅผ boolean์ผ๋ก ์ ์ธํด์คฌ๋ค.
์ด์ for๋ฌธ์ ํตํด ๋ฐฉํฅ๋ฒกํฐ(์,ํ,์ข,์ฐ)๋ก ์ด๋์ ํ๊ฒ๋ ํ ๋ฐ ์ด ๋ ์ด๋์ ํ๋ ์๊ฐ ์์นํด์๋ ๋ฐํ์ ์ฌ๋ผ์ง๋ฏ๋ก ํ์ฌ ๋ฐํ์ธ board[me์ Row๊ฐ][me์ Col๊ฐ] = 0์ ํด์ฃผ๊ณ ์ํ์ข์ฐ ์ด๋์ ์์ํ๋ค.
=> ๋ง์ฝ ์ด๋ํ๋ ค๋ ๊ณณ์ด map์ ๋ฒ์ด๋๊ฑฐ๋ ๋ฐํ์ด ์์ผ๋ฉด continue๋ฅผ ํตํด ์ด๋ํ์ง ์๊ณ ์ด์ ๊ฑธ๋ฆฌ์ง ์์๋ค๋ฉด ์ด๋์ด ๊ฐ๋ฅํ๋ฏ๋ก canMove๋ฅผ true๋ก ๋ณ๊ฒฝํด์ฃผ์๋ค.
๊ทธ๋ฆฌ๊ณ int[] result๋ฅผ ํตํด ํด๋น ๋ฐฉํฅ์ผ๋ก ์ด๋ํ์ ๋ ๋ค์ ํ๋ ์ด์ด์ ์น๋ฆฌ ์ฌ๋ถ์ ๊ทธ ๋์ ํด ์๋ฅผ ๋ฐํ๋ฐ๋ ์ฌ๊ท์ ๊ฒฐ๊ณผ๋ฅผ ๋ฐ์์จ๋ค.
(๋ค์ ํ๋ ์ด์ด์ ์ด๋์ ํธ์ถํ ๋๋ ํ๋ ์ด์ด๊ฐ ๋ฐ๋๋ฏ๋ก opponent์ me์ ์์น๋ฅผ ๋ฐ๊ฟ์ ํธ์ถํด์ค์ผํจ)
=> ์ด๊ฒ ์ดํด๊ฐ ์๋ ์ ์๋๋ฐ ๋ง์ฝ A๊ฐ ์์ชฝ์ผ๋ก ์ด๋ํ๊ณ ๋์ B๊ฐ ๊ทธ์ ๋ง์ถฐ ์ด๋์ํ๊ณ ๋, B๊ฐ ์ด๋์ ํ์ ๋์ ๋ง์ถฐ A๊ฐ ์ด๋ํ๊ณ ์ด๋ฐ์์ผ๋ก B, A, B, A ... ๋ฅผ ํ๊ฒ ๋๋ฉด ๊ฒฐ๊ตญ ๋ง์ง๋ง์ ๋๊ตฐ๊ฐ ์ด๋์ ๋ชปํ๊ฑฐ๋ ๋ฐํ์ด ์ฌ๋ผ์ง๋ฉด ๊ทธ๋ ํ๋ ์ด์ด์ ์น๋ฆฌ, ํจ๋ฐฐ ์ฌ๋ถ์ ํด์๋ฅผ ๋ด์ return ํ๊ฒ ๋๋๋ฐ ์ด๋ฅผ ๋ณด๊ณ ๊ทธ ์๊ฐ ์ต์ ์ ์ ํ(์น๋ฆฌํ ์ ์์ผ๋ฉด ์ต๋ํ ์ ์ํด์ผ๋ก ์น๋ฆฌํ ์ ์๋ ๋ฐฉํฅ์ผ๋ก ์ด๋, ๋ฌด์กฐ๊ฑด ํจ๋ฐฐ๋ผ๋ฉด ์ต๋ํ ๋ง์ ํด์ ๋ฒํธ ์ ์๋ ๋ฐฉํฅ์ผ๋ก ์ด๋)์ ํ๊ฒ ๋๋ฉฐ ๋ง์ง๋ง์๋ ๊ฒฐ๊ตญ ์ฒ์ ํธ์ถํ A ํ๋ ์ด์ด ์ํฉ์์๋ ์น๋ฆฌ, ํจ๋ฐฐ์ ์ฌ๋ถ์ ๊ฐ ๊ฒฐ๊ณผ์ ๋ฐ๋ฅธ ํด ์๋ฅผ ํ์ธํ ์ ์์
์ผ๋จ for๋ฌธ์ ๋งจ ์ฒ์ ๋ค์ด๊ฐ์ ๋๋ฅผ ์๊ฐํด๋ณด์
๋ฐฉํฅ๋ฒกํฐ์ ๋ฐ๋ผ ํ์ฌ ์์น์ ์์ชฝ์ผ๋ก ์ด๋ํ ํ ๋ฐ ๊ฒฐ๊ตญ ๊ฐ ์ฌ๊ท ํธ์ถ๋ง๋ค ์ต์ ์ ์ ํ์ ํด์ ์ป์ ๊ฒฐ๊ณผ๋ฌผ์ด {1, 3} ์ด๋ผ๊ณ ํ์
๊ทธ๋ผ {์น๋ฆฌ ์ฌ๋ถ, ํด ์} ์ธ๋ฐ 1์ด๋ฉด ํจ๋ฐฐ๋ฅผ ์๋ฏธํ๋ค
์ด๋ ์กฐ์ฌํด์ผํ ๊ฑด ์น๋ฆฌ ์ฌ๋ถ๋ ๋ค์ ํ๋ ์ด์ด๋ฅผ ํธ์ถํ์ ๋์ ๊ฒฐ๊ณผ์ด๋ฏ๋ก ๋ด๊ฐ ์์ชฝ์ผ๋ก ์ด๋ํ์ ๋ B์ ์น๋ฆฌ์ฌ๋ถ๊ฐ ๋ฐํ๋๋ ๊ฒ์ด๋ค.
์ฆ, {1, 3}์ B๊ฐ 3ํด๋ง์ ํจ๋ฐฐ๋ฅผ ํ ๊ฒ์ ์๋ฏธํ๋ฏ๋ก A ์ ์ฅ์์๋ ์น๋ฆฌํ๋ ๊ฒฐ๊ณผ์ธ ๊ฒ์ด๋ค.
=> ๊ทธ๋์ result[0] == 1 ์ด๋ผ๋ฉด A์ ์น๋ฆฌ์ด๊ณ ์ด ๋๋ ์ต๋ํ ์ ์ ํด์ผ๋ก ์น๋ฆฌ๋ฅผ ํด์ผํ๋ฏ๋ก Math.min์ ํตํด ์น๋ฆฌํ์ ๋ ๊ฐ์ฅ ์ ์ ํด ์๋ฅผ ๋ด๊ณ ์๋ winTurn ๋ณ์๋ฅผ ๊ฐฑ์ ํด์ค๋ค
(์ด ๋ ์ถ๊ฐ๋ก ์น๋ฆฌ๊ฐ ๊ฐ๋ฅํ์ง๋ฅผ ๋ํ๋ด๋ canWin ๋ณ์๋ true๋ก ๊ฐฑ์ ํด์ค์ผํ๋ค)
๋ฐ๋๋ก result[0] == 0 ์ด๋ผ๋ฉด A์ ์ฅ์์๋ B๊ฐ ์น๋ฆฌํ๋ ๊ฒ์ด๋ฏ๋ก ํจ๋ฐฐ๋ฅผ ํ๊ฒ๋๋ค.
์ด ๋๋ ์ต๋ํ ์ค๋ ๋ฒํฐ๋ ํด์ ๋ํ๋ด๋ loseTurn์ Math.max๋ก ๊ฐฑ์ ํด์ค๋ค.
์ด๋ ๊ฒ for๋ฌธ์ ๋ค ๋์์ ์,ํ,์ข,์ฐ์ ์ด๋์ ๋ฐ๋ฅธ {์น๋ฆฌ ์ฌ๋ถ, ํด ์}๋ฅผ ์์๋ด์ ์ต์ ์ ์ด๋ ๋ฐฉํฅ์ ์ฐพ์์ผ๋ฉด ํ์์ ์ํด ์ ๊ฑฐํ๋ ๋ฐํ์ ๋ค์ ๋ณต๊ตฌํด์ค๋ค.
=> ์ด๋ฅผ ๋ณต๊ตฌํ์ง ์์ผ๋ฉด ๊ฐ ํด์ ํ์ํ๋ฉด์ ๋ฐํ์ด ์ค๊ฐ์ค๊ฐ ์ฌ๋ผ์ ธ์๋ ์ํ๊ฐ ์ ์ง๋๊ธฐ์ ์ฌ๋ฐ๋ฅธ ๊ฒฐ๊ณผ๋ฅผ ์ฐพ์ ์ ์์
๊ทธ๋ผ for๋ฌธ์ ๋ชจ๋ ๋์์ผ๋ฉด ํ์ฌ ํ๋ ์ด์ด๊ฐ ์น๋ฆฌ๋ฅผ ํ ์ ์๋์ง(canWin), ์ด๋ํ ๊ณณ์ด ์๋์ง(canMove), ๋ง์ฝ ์น๋ฆฌํ๋ค๋ฉด ๊ฐ์ฅ ์ ์ ํด์ด ๋ช์ธ์ง(winTurn), ๋ง์ฝ ํจ๋ฐฐํ๋ค๋ฉด ๊ฐ์ฅ ์ค๋ ๋ฒํด ํด์ด ๋ช์ธ์ง(loseTurn)์ด ๋ชจ๋ ์ฌ๋ฐ๋ฅด๊ฒ ๋ด๊ฒจ์๊ฒ๋๋ค.
๋ง์ฝ canMove๊ฐ false๋ผ์ ์ด๋์ ํ ์ ์๋ค๋ฉด ํด๋น ํ๋ ์ด์ด๋ ํจ๋ฐฐ๋ฅผ ํ๊ฒ ๋๋ฏ๋ก {1, 0}์ ํตํด ํจ๋ฐฐ๋ฅผ ๋ํ๋ด๋ 1๊ณผ ์ด๋์ ํ์ง ์์์ผ๋ฏ๋ก ํด ์ 0์ return ํด์ค๋ค
๋ง์ฝ ์์ง์ผ ์ ์๋ค๋ฉด canWin์ ์ดํด๋ด์ผํ๋ค.
ํ์ฌ ํ๋ ์ด์ด๊ฐ ํน์ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ์ ๋ ์น๋ฆฌํ๋ ๊ฒฝ์ฐ๊ฐ ์์๋ค๋ฉด ๋ฌด์กฐ๊ฑด ์น๋ฆฌ๋ฅผ ํ๋ ๋ฐฉํฅ์ผ๋ก ์ด๋์ ํด์ผํ๋ฏ๋ก {0, winTurn + 1}์ ๋ด์์ return ํด์ฃผ๊ณ ์น๋ฆฌํ๋ ๊ฒฝ์ฐ๊ฐ ์์ด์ canWin์ด false๋ผ๋ฉด ๊ฐ์ฅ ์ค๋ ๋ฒํฐ๋ ๋ฐฉํฅ์ผ๋ก ์ด๋์ ํด์ผํ๋ฏ๋ก {1, loseTurn + 1}์ ๋ด์์ return ํด์ค๋ค.
=> ์ฐธ๊ณ ๋ก winTurn๊ณผ loseTurn์ ๊ฐ๊ฐ ์น๋ฆฌ, ํจ๋ฐฐ ์ ๊ฐ์ฅ ์งง์ ํด๊ณผ ๊ฐ์ฅ ๊ธด ํด์ด ์ ์ฅ๋์ด ์์ ๊ฒ์ด๊ณ +1์ ํด์ค ์ด์ ๋ winTurn, loseTurn์ ๋ค์ ํ๋ ์ด์ด์ ์ด๋์ ํธ์ถํ์ ๋์ ๊ฒฐ๊ณผ ๊ฐ์ด๋ฏ๋ก ํ์ฌ ํ๋ ์ด์ด์ ์ด๋์ด ๋ฐ์๋์ด ์์ง ์์์ +1์ ํด์ค ๊ฒ์ด๋ค.
์ฝ๊ฒ ์๊ฐํด๋ณด๋ฉด A๊ฐ for๋ฌธ์ ๋๋ฉด์ ์ค๋ฅธ์ชฝ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ์ ๋์ ์ํฉ์ผ๋ก B๋ฅผ ํธ์ถํด์ ํจ๋ฐฐ, 3์ด๋ผ๋ ๊ฒฐ๊ณผ๋ฅผ ๋ฐ์๋ค๋ฉด ๋ด๊ฐ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํ์ ๋ B๊ฐ 3ํด๋ง์ ํจ๋ฐฐ๋ฅผ ํ๋ค๋ ์๋ฏธ๋ก winTurn์ 3์ด ๋ด๊ฒจ์์ ๊ฒ์ด๋ค.
์ฆ, ๋ด๊ฐ ์ค๋ฅธ์ชฝ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ๋ฉด 3ํด๋ง์ B๋ก๋ถํฐ ์น๋ฆฌ๋ฅผ ํ ์ ์๋ค๋ ์๋ฏธ์ด๋ฏ๋ก ํ์ฌ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํ๋ ํด์ +1 ํด์ค์ผ A๊ฐ B๋ก๋ถํฐ ์น๋ฆฌํ์ ๋์ ์ ์ฒด ํด์ ๊ตฌํ ์ ์๋ค.
๊ฒฐ๊ตญ dfs๊ฐ ๋๋๊ฒ ๋๋ฉด solution ํจ์์ ์๋ result์๋ ์ฒ์ ์์์ธ A์ ์น๋ฆฌ ์ฌ๋ถ์ ๊ทธ ๋์ ์ต์ ์ ํด ์๊ฐ ๋ด๊ฒจ์์ ๊ฒ์ด๊ณ ์ด ํด ์๋ฅผ ๋ฐํํด์ฃผ๋ฉด ๋๋๋ค.
์ ์ฒด ์ฝ๋
class Solution {
// ์ํ์ข์ฐ ๋ฐฉํ๋ฒกํฐ
int[] dRow = {-1, 1, 0 ,0};
int[] dCol = {0, 0, -1, 1};
boolean isRange(int row, int col, int[][] board) {
if(row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
return false;
}
if(board[row][col] == 0) {
return false;
}
return true;
}
// ๋ฐํ๊ฐ: {์น๋ฆฌ ์ฌ๋ถ(0: ์น๋ฆฌ, 1: ํจ๋ฐฐ), ํด ์}
int[] dfs(int[] me, int[] opponent, int[][] board) {
int meRow = me[0];
int meCol = me[1];
// ํ์ฌ ๋ด ๋ฐํ์ด ์์ด์ง๋ฉด ํจ๋ฐฐ
if(board[meRow][meCol] == 0) {
return new int[] {1, 0}; // {ํจ๋ฐฐ, 0ํด}
}
// winTurn์ ์ต์๊ฐ์ ์ฐพ์์ผ ํ๋ฏ๋ก ํฐ ๊ฐ์ผ๋ก ์ด๊ธฐํ
int winTurn = 26; // ์ต๋ 5 * 5 ์ด๋ฏ๋ก 26์ผ๋ก ์ด๊ธฐํ
// loseTurn์ ์ต๋๊ฐ์ ์ฐพ์์ผ ํ๋ฏ๋ก ์์ ๊ฐ์ผ๋ก ์ด๊ธฐํ
int loseTurn = 0;
boolean canWin = false; // ์ด๊ธธ ์ ์๋์ง ์ฒดํฌ
boolean canMove = false; // ์์ง์ผ ์ ์๋์ง ์ฒดํฌ
board[meRow][meCol] = 0; // ๋ฐํ ์ญ์
for(int d = 0; d < 4; d++) {
int newRow = meRow + dRow[d];
int newCol = meCol + dCol[d];
if(!isRange(newRow, newCol, board)) continue;
canMove = true; // ํ ๋ฒ์ด๋ผ๋ ์์ง์ผ ์ ์์
int[] result = dfs(opponent, new int[] {newRow, newCol}, board);
// result[0] == 1 (์๋๋ฐฉ ํจ๋ฐฐ) -> ๋๋ ์น๋ฆฌ
if(result[0] == 1) {
winTurn = Math.min(winTurn, result[1]);
canWin = true;
} else { // result[0] == 0 (์๋๋ฐฉ ์น๋ฆฌ) -> ๋๋ ํจ๋ฐฐ
loseTurn = Math.max(loseTurn, result[1]);
}
}
board[meRow][meCol] = 1; // ๋ฐํ ๋ณต๊ตฌ
// ์์ง์ผ ๊ณณ์ด ์์ด์ ์ก์ ๊ฒฝ์ฐ
if(!canMove) {
return new int[] {1, 0}; // {ํจ๋ฐฐ, 0ํด}
}
if(canWin) {
return new int[] {0, winTurn + 1}; // ๋ด ํด(+1) ํฌํจ
} else {
return new int[] {1, loseTurn + 1}; // ๋ด ํด(+1) ํฌํจ
}
}
public int solution(int[][] board, int[] aloc, int[] bloc) {
int[] result = dfs(aloc, bloc, board);
return result[1];
}
}
'๐ฅ Algorithm > ์์ ํ์' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| [ํ๋ก๊ทธ๋๋จธ์ค] ์ฒด์ก๋ํ (JAVA ํ์ด) (0) | 2025.10.31 |
|---|---|
| [ํ๋ก๊ทธ๋๋จธ์ค] ์๊ณผ ๋๋ (JAVA ํ์ด) (0) | 2025.10.26 |
| [ํ๋ก๊ทธ๋๋จธ์ค] ์๊ถ๋ํ (JAVA ํ์ด) (0) | 2025.10.25 |