Problem
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์นด๋ ์ง ๋ง์ถ๊ธฐ
[[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16
programmers.co.kr
Solution
๋ชจ๋ ์นด๋๋ฅผ ๋ค์ง๋ ์ต์ ์กฐ์ํ์๋ฅผ ์ฐพ์์ผ ํ๋ ๋ฌธ์ ์ ๋๋ค.
(BFS๋ฅผ ๊ตฌํํ๋ ๋ฒ๊ณผ ์์ด๊ตฌํ๋ ๋ฒ์ ์์์ผ ๊ตฌํํ๊ธฐ ์์ํ์ค๊ฒ๋๋ค.)
1. ์นด๋๋ฅผ ๋ค์ง๋ ์์๋ฅผ ์ ํ๊ธฐ(์์ด ๊ตฌํ๋ ๋ฐฉ๋ฒ ์๊ธฐ)
๋ง์ฝ 1,2,3 ์นด๋๊ฐ ์๋ค๋ฉด 1 - 2 - 3, 1 - 3 - 2, 2 - 1 - 3... ๋ฑ์ผ๋ก ๋ค์ง์ ์ ์์ต๋๋ค.
์์ด์ ๊ตฌํ๋ ๋ฐฉ๋ฒ์ ์ฌ๊ท ํจ์๋ฅผ ์ฌ์ฉํด ํด๋น ํ๋์ฉ ์ซ์๋ฅผ ์ง์๋๊ฐ๋ฉด์ depth์ ์ ์ฅํด์ค๋๋ค.
ํ์ง๋ง ์นด๋๋ ๊ฐ ๊ฐ 2์ฅ์ฉ ์์ผ๋ฏ๋ก ๋๊ฐ์ ์ซ์ ์นด๋๋ผ๋ ๋จผ์ ๋ค์ง์ ์นด๋ ์์๋ ์ ํด์ค์ผ ํฉ๋๋ค.
(startCardGame์ ์ฐธ์กฐํด์ฃผ์ธ์!)
2. BFS๋ก ๋ชจ๋ ์ด๋์ ๋ํ ์กฐ์ ํ์ ๊ตฌํ๊ธฐ
์ผ์ชฝ,์ค๋ฅธ์ชฝ,์๋์ชฝ,์์ชฝ์ผ๋ก ์ด๋ํ๋ ๊ฒ๊ณผ ctrl์ ๋๋ฅด๊ณ ์ผ์ชฝ,์ค๋ฅธ์ชฝ,์๋์ชฝ,์์ชฝ๋ก ์ด๋ํ๋ ๊ฒฝ์ฐ๊ฐ ์์ผ๋ฏ๋ก ์ด 8๊ฐ์ง๋ก
์ด๋ํ์ ๋ ์กฐ์ ํ์๋ฅผ ๊ตฌํด์ผ ํฉ๋๋ค.
์ด ๋ BFS๋ก ์ด๋์ ๋ํ ๊ฐ์ queue์ ๋ฃ์ด๋๊ณ queue์ ๊ฐ์ฅ ์ฒซ๋ฒ์งธ ๊ฐ์ ์ญ์ ํด ๋๊ฐ๋ฉด์ ๊ตฌํ ์ ์์ต๋๋ค.
๋ํ 4x4 Bool์ ๋ด์ ๋ฐฐ์ด์ ๋ง๋ค์ด์ ํด๋น ์์น๋ฅผ ๋ฐฉ๋ฌธํ๋์ง ์ํ๋์ง ํ์ธํด์ค๋๋ค.
(moveCurrentToGoal๊ณผ moveBFS๋ฅผ ์ฐธ๊ณ ํด์ฃผ์ธ์!)
3. ๋ชจ๋ ๊ฒฝ์ฐ์ ์์์ ๊ฐ์ฅ ์์ ๊ฐ ์ฐพ๊ธฐ
์ ๋ต(answer) ๋ณ์๋ฅผ ์ ์์์ ๊ฐ์ฅ ํฐ ๊ฐ์ธ Int.max๋ก ๋์ต๋๋ค.
์นด๋๋ฅผ ๋ค์ง์ ๋๋ง๋ค depth์ ์ซ์๋ค์ ๋ด์๋๊ณ ๋ชจ๋ ์ซ์๋ค์ด ๋ค์ง์ด์ก์๋ ์ฆ, depth์ ์นด๋๊ฐฏ์/2๋งํผ์ ์ซ์๊ฐ ์ฑ์์ก์๋
answer์ count๋ฅผ ๋น๊ตํด ๋ ์๋ค๋ฉด answer๋ฅผ count๋ก ๋ฐ๊ฟ์ค๋๋ค.
์ด๋ ๊ฒ ๋ชจ๋ ์์ด์ ๋ํ ์กฐ์ํ์๋ฅผ ๊ตฌํ๊ณ ๋ ์์ ๊ฐ์ผ๋ก answer๋ฅผ ๋ฐ๊ฟ์ค๋๋ค.
๋ง์ง๋ง์ผ๋ก answer์ ์ด์ฐจํผ ์นด๋๋ค์ ๋ค์ง์ด์ง ๋๋ง๋ค +1์ด๋ฏ๋ก ์นด๋์ ๊ฐฏ์๋งํผ์ ๋ํด์ฃผ๊ณ return ํด์ค๋๋ค.
(solution์ ์ฐธ๊ณ ํด์ฃผ์ธ์!)
Source Code
P.S
์ฒ์์ ๋ชจ๋ ์นด๋๋ฅผ ๋ค์ง๋ ๊ฒฝ์ฐ์ ์๋ ๊ทธ๋ฅ ๋ชจ๋ ์นด๋๋ฅผ ํ์ํ๊ณ ๋ค์ง์ ์นด๋๋ฅผ ์ง์ฐ๊ณ ๋ ๋จ์ ์นด๋๋ค์
๋๊ฐ์ด ๋ฐ๋ณตํด์ฃผ๋ฉด ๋์ง ์๋? ๋ผ๊ณ ์๊ฐํ๋๋ฐ ์๋๋ค..
๊ทผ๋ฐ ์ค์ ๋ก ์์ด๋ ์ซ์๋ค์ ๋ณด๋ฉด ์์ด๊ณผ ๋๊ฐ์ด ์์ด๊ธดํ๋๋ฐ.. ์ ์๋ ๊น?
BFS๋ก ๊ตฌํํ๊ธฐ ์ ์๋ ํ์ฌ x,y์ ๋ชฉ์ ์ง์ x,y๋ฅผ ์ฐจ์ด๋ฅผ ๋น๊ตํด์ x๋จผ์ ๋ง์ถ๊ณ y๋ฅผ ๋ง์ถ๋์ y ๋จผ์ ๋ง์ถ๊ณ x๋ฅผ ๋ง์ถ๋๋ฅผ
๊ตฌํ๋ฉด ๋๊ฒ ์งํ๋๋ฐ ์๋์ ๊ฐ์ด 4์์ 4๋ก ์ด๋ํ๋ ๊ฒฝ์ฐ๋ y๋ฅผ ํ์นธ๋ง ์์ง์ด๊ณ x์์ ctrl๋ก ์์ง์ด๊ณ
๋ค์ y๋ฅผ ์์ง์ฌ์ผ ๋๋ฏ๋ก ๋ชจ๋ ์ด๋์ ๋ํ ์กฐ์ ํ์๋ฅผ ๊ตฌํด์ค์ผ ํ๋ค.
์ด๊ฑฐ ํ ๋ฌธ์ ํธ๋๋ฐ ๊ฑฐ์ ์ผ์ฃผ์ผ๊ฑธ๋ฆฐ๊ฑฐ ๊ฐ๋ค....
๊ณ ์ง๋ ๋ง์ด ๋ถ๋ฆฌ๊ณ ๋๋ง์ ๋ฐฉ์์ผ๋ก ํ๊ฑฐ์ผ๋ผ๊ณ ์๊ฐํด์ ์ค๋ ๊ฑธ๋ฆฐ๊ฑฐ ๊ฐ๋ค...
๋ค์๋ถํฐ๋ ๋ด๋ ค๋๊ณ ๋ฐฐ์ฐ๋ ๋ง์์ผ๋ก ์ฝ๋๋ฅผ ์์ฑํด์ผ๊ฒ ๋ค.
Reference
2021 ์นด์นด์ค ์ ์ ๊ณต์ฑ 1์ฐจ ์จ๋ผ์ธ ์ฝ๋ฉ ํ ์คํธ for Tech developers ๋ฌธ์ ํด์ค
์ง๋ 2020๋ 9์ 12์ผ ํ ์์ผ ์คํ 2์๋ถํฐ 7์๊น์ง 5์๊ฐ ๋์ 2021 ์นด์นด์ค ์ ์ ๊ฐ๋ฐ์ ๊ณต์ฑ 1์ฐจ ์ฝ๋ฉ ํ ์คํธ๊ฐ ์งํ๋์์ต๋๋ค. ํ ์คํธ์๋ ์ด 7๊ฐ์ ๋ฌธ์ ๊ฐ ์ถ์ ๋์์ผ๋ฉฐ, ๊ฐ๋ฐ ์ธ์ด๋ C++, Java, Jav
tech.kakao.com
'๐ Problem Solution' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Swift] 2018 KAKAO BLIND RECRUITMENT [1์ฐจ] ์ถ์ ํธ๋ํฝ (0) | 2021.05.19 |
---|---|
[Swift] 2020 KAKAO INTERNSHIP ํคํจ๋ ๋๋ฅด๊ธฐ (0) | 2021.05.08 |
[Swift] 2021 KAKAO BLIND RECRUITMENT ๊ด๊ณ ์ฝ์ (0) | 2021.04.11 |
[Swift] ๋ฐฑ์ค while๋ฌธ 1,2,3๋ฒ (0) | 2020.02.01 |
๋ฐฑ์คํ๋ก๊ทธ๋๋ฐ for๋ฌธ 10๋ฒ,11๋ฒ Swift (0) | 2020.01.29 |
๋๊ธ