1) ๋ฌธ์ ์ค๋ช
- ROR ๊ฒ์์ ๋ ํ์ผ๋ก ๋๋์ด์ ์งํํ๋ฉฐ, ์๋ ํ ์ง์์ ๋จผ์ ํ๊ดดํ๋ฉด ์ด๊ธฐ๋ ๊ฒ์์ ๋๋ค.
- ๋ฐ๋ผ์, ๊ฐ ํ์ ์๋ ํ ์ง์์ ์ต๋ํ ๋นจ๋ฆฌ ๋์ฐฉํ๋ ๊ฒ์ด ์ ๋ฆฌํฉ๋๋ค.
- ์ง๊ธ๋ถํฐ ๋น์ ์ ํ ํ์ ํ์์ด ๋์ด ๊ฒ์์ ์งํํ๋ ค๊ณ ํฉ๋๋ค.
- ๋ค์์ 5 x 5 ํฌ๊ธฐ์ ๋งต์, ๋น์ ์ ์บ๋ฆญํฐ๊ฐ (ํ: 1, ์ด: 1) ์์น์ ์๊ณ , ์๋ ํ ์ง์์ (ํ: 5, ์ด: 5) ์์น์ ์๋ ๊ฒฝ์ฐ์ ์์์ ๋๋ค.
- ์ ๊ทธ๋ฆผ์์ ๊ฒ์์ ๋ถ๋ถ์ ๋ฒฝ์ผ๋ก ๋งํ์์ด ๊ฐ ์ ์๋ ๊ธธ์ด๋ฉฐ, ํฐ์ ๋ถ๋ถ์ ๊ฐ ์ ์๋ ๊ธธ์ ๋๋ค.
- ์บ๋ฆญํฐ๊ฐ ์์ง์ผ ๋๋ ๋, ์, ๋จ, ๋ถ ๋ฐฉํฅ์ผ๋ก ํ ์นธ์ฉ ์ด๋ํ๋ฉฐ, ๊ฒ์ ๋งต์ ๋ฒ์ด๋ ๊ธธ์ ๊ฐ ์ ์์ต๋๋ค.
- ์๋ ์์๋ ์บ๋ฆญํฐ๊ฐ ์๋ ํ ์ง์์ผ๋ก ๊ฐ๋ ๋ ๊ฐ์ง ๋ฐฉ๋ฒ์ ๋ํ๋ด๊ณ ์์ต๋๋ค.
(1) ์ฒซ ๋ฒ์งธ ๋ฐฉ๋ฒ
- 11๊ฐ์ ์นธ์ ์ง๋์ ์๋ ํ ์ง์์ ๋์ฐฉํ์ต๋๋ค.
(2) ๋ ๋ฒ์งธ ๋ฐฉ๋ฒ
- 15๊ฐ์ ์นธ์ ์ง๋์ ์๋ํ ์ง์์ ๋์ฐฉํ์ต๋๋ค.
- ์ ์์์์๋ ์ฒซ ๋ฒ์งธ ๋ฐฉ๋ฒ๋ณด๋ค ๋ ๋น ๋ฅด๊ฒ ์๋ํ ์ง์์ ๋์ฐฉํ๋ ๋ฐฉ๋ฒ์ ์์ผ๋ฏ๋ก, ์ด ๋ฐฉ๋ฒ์ด ์๋ ํ ์ง์์ผ๋ก ๊ฐ๋ ๊ฐ์ฅ ๋น ๋ฅธ ๋ฐฉ๋ฒ์ ๋๋ค.
- ๋ง์ฝ, ์๋ ํ์ด ์์ ์ ํ ์ง์ ์ฃผ์์ ๋ฒฝ์ ์ธ์๋์๋ค๋ฉด ์๋ ํ ์ง์์ ๋์ฐฉํ์ง ๋ชปํ ์๋ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, ๋ค์๊ณผ ๊ฐ์ ๊ฒฝ์ฐ์ ๋น์ ์ ์บ๋ฆญํฐ๋ ์๋ ํ ์ง์์ ๋์ฐฉํ ์ ์์ต๋๋ค.
- ๊ฒ์ ๋งต์ ์ํ maps๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์บ๋ฆญํฐ๊ฐ ์๋ ํ ์ง์์ ๋์ฐฉํ๊ธฐ ์ํด์ ์ง๋๊ฐ์ผ ํ๋ ์นธ์ ๊ฐ์์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ๋จ, ์๋ ํ ์ง์์ ๋์ฐฉํ ์ ์์ ๋๋ -1์ return ํด์ฃผ์ธ์.
2) ์ ํ ์ฌํญ
- maps๋ n x m ํฌ๊ธฐ์ ๊ฒ์ ๋งต์ ์ํ๊ฐ ๋ค์ด์๋ 2์ฐจ์ ๋ฐฐ์ด๋ก, n๊ณผ m์ ๊ฐ๊ฐ 1 ์ด์ 100 ์ดํ์ ์์ฐ์์ ๋๋ค.
- n๊ณผ m์ ์๋ก ๊ฐ์ ์๋, ๋ค๋ฅผ ์๋ ์์ง๋ง, n๊ณผ m์ด ๋ชจ๋ 1์ธ ๊ฒฝ์ฐ๋ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
- maps๋ 0๊ณผ 1๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, 0์ ๋ฒฝ์ด ์๋ ์๋ฆฌ, 1์ ๋ฒฝ์ด ์๋ ์๋ฆฌ๋ฅผ ๋ํ๋ ๋๋ค.
- ์ฒ์์ ์บ๋ฆญํฐ๋ ๊ฒ์ ๋งต์ ์ข์ธก ์๋จ์ธ (1, 1) ์์น์ ์์ผ๋ฉฐ, ์๋๋ฐฉ ์ง์์ ๊ฒ์ ๋งต์ ์ฐ์ธก ํ๋จ์ธ (n, m) ์์น์ ์์ต๋๋ค.
3) ์ ์ถ๋ ฅ ์์
maps answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1
4) ์ ์ถ๋ ฅ ์์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
์ฃผ์ด์ง ๋ฐ์ดํฐ๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์บ๋ฆญํฐ๊ฐ ์ ํ์ ์ง์๊น์ง ์ด๋ํ๋ ๊ฐ์ฅ ๋น ๋ฅธ ๊ธธ์ ๋ค์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ต๋๋ค.
๋ฐ๋ผ์ ์ด 11์นธ์ ์บ๋ฆญํฐ๊ฐ ์ง๋๊ฐ์ผ๋ฏ๋ก 11์ return ํ๋ฉด ๋ฉ๋๋ค.
์
์ถ๋ ฅ ์ #2
๋ฌธ์ ์ ์์์ ๊ฐ์ผ๋ฉฐ, ์๋ ํ ์ง์์ ๋๋ฌํ ๋ฐฉ๋ฒ์ด ์์ต๋๋ค. ๋ฐ๋ผ์ -1์ return ํฉ๋๋ค.
5) ํ์ด
from collections import deque
# row, col์ด ์ ํจ ๋ฒ์ ๋ด์ ์๋์ง ํ์ธํ๋ ํจ์
def isInRange(row, col, max_row, max_col):
return (0 <= row < max_row) and (0 <= col < max_col)
def solution(maps):
# max_row, max_col, visited ๋ฐฐ์ด, direction ๋ฐฐ์ด (์, ํ, ์ข, ์ฐ) ์ด๊ธฐํ
shortestPath = -1
max_row = len(maps)
max_col = len(maps[0])
visited = [[False] * max_col for _ in range(max_row)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Queue ์์ฑ --> (row, col, distance)
q = deque()
q.append((0, 0, 1))
visited[0][0] = True
while q:
row, col, dist = q.popleft()
# ๋ชฉ์ ์ง์ธ ๊ฒฝ์ฐ, ๊ฒฝ๋ก return
if row == max_row - 1 and col == max_col - 1:
return dist
# ์, ํ, ์ข, ์ฐ์ ๋ฐ๋ผ ์ด๋
for dr, dc in directions:
next_row = row + dr
next_col = col + dc
# ์ ํจ ๋ฒ์ ๋ด์ ์๋์ง ํ์ธ
if isInRange(next_row, next_col, max_row, max_col):
# ๋ฒฝ์ด ์๋ ์ํ์ด๊ณ , ๋ฐฉ๋ฌธํ์ง ์์ ๊ฒฝ์ฐ์ธ์ง ํ์ธ
if maps[next_row][next_col] == 1 and visited[next_row][next_col] == False:
q.append((next_row, next_col, dist + 1))
visited[next_row][next_col] = True
return shortestPath
[Reference]
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๋ฐ์ํ
'๐ฏ Coding Test > ์๊ณ ๋ฆฌ์ฆ ํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ๋ก๊ทธ๋๋จธ์ค (Lv 2) - ์ฐ์ ๋ถ๋ถ ์์ด ํฉ์ ๊ฐ์ (1) | 2023.08.22 |
---|---|
ํ๋ก๊ทธ๋๋จธ์ค (Lv 2) - ํ๋ ฌ์ ๊ณฑ์ (1) | 2023.08.21 |
ํ๋ก๊ทธ๋๋จธ์ค (Lv 2) - ๊ตฌ๋ช ๋ณดํธ (1) | 2023.08.17 |
ํ๋ก๊ทธ๋๋จธ์ค (Lv 2) - ์์ด ๋๋ง์๊ธฐ (1) | 2023.08.17 |
ํ๋ก๊ทธ๋๋จธ์ค (Lv 2) - ์นดํซ (1) | 2023.08.17 |