์ฝ๋ฉํ ์คํธ ์ฐ์ต > ์ฐ์ต๋ฌธ์ > ๋ฆฌ์ฝ์ณ ๋ก๋ด (JS) ๋ฌธ์ ํ์ด
๐ฅ๋ฌธ์
https://school.programmers.co.kr/learn/courses/30/lessons/169199
๐ฅํ์ด
์ฒ์์ DFS๋ก ๋ฌธ์ ํ์ด ์ ๊ทผ์ ํ๋๋ฐ ์ฌ๋ฌ์ผ์ด์ค์์ ์๊ฐ์ด๊ณผ๋ก ๋ฌธ์ ํ์ด์ ์คํจํ๋ค. ๊ทธ๋์ ๋ค๋ฅธ ์ฌ๋์ ํ์ด๋ฅผ ๋ดค๋๋ฐ BFS๋ก ๋ฌธ์ ์ ์ ๊ทผํ๊ณ ์์๊ณ ๋ด ์๊ฐ์๋ ์ด ์ ๊ทผ๋ฒ์ด ์๊ฐ์ด ์๋ฑํ ์ ๊ฒ ๋ค๊บผ๋ ์๊ฐ์ด ๋ค์ด BFS๋ก ๋ค์ ๋ฌธ์ ํ์ด๋ฅผ ์งํํ๋ค.
์ฐ๋ฆฌ๋ ๋ชฉํ์์น์ ๋๋ฌํ๊ธฐ ์ํ ์ต์ํ์ ๋ฏธ๋๋ฌ์ง ์๋ฅผ ๊ตฌํ๊ธฐ ๋๋ฌธ์ ๊ตณ์ด ๋ชจ๋ ๋ฐฉ์์ ๋ค ํ์ํ ํ์์์ด n๋ฒ ์์ง์์ ๋ ์ด๋ํ ์์น์ ๋ช๋ฒ ์ด๋ํ๋์ง ๊ฐ๋ง ๊ธฐ์ตํ๊ณ ์ด๋ํ๋ ํฌ์ธํธ๋ฅผ ์ฒดํฌ๋ง ํ๋ฉด๋๋ค. (์ฝ๋๋ฅผ ๋ณด๋ฉด ์๊ฒ ์ง๋ง ํ๋ฉด ์ง๋๊ฐ ํฌ์ธํธ๋ visit_map์ ํ๊ธฐํ์๋ค.)
function solution(board) {
let min = undefined
let [start_x,start_y]=[undefined,undefined]
for(let i=0; i<=board.length-1; ++i){
for(let j=0; j<=board[0].length-1; ++j){
if(board[i][j]==='R'){
start_x =i
start_y =j
}
}
}
let visit_map = Array.from({length:board.length},(_)=>{
return Array(board[0].length).fill(false)
})
// ๋์๋จ๋ถ
let dx =[0,0,1,-1] , dy =[1,-1,0,0]
let queue = [[start_x,start_y,0]]
visit_map[start_x][start_y]=true
while(queue.length){
let [x,y,count] = queue.shift()
if(board[x][y]==='G'){
min =count
break;
}
dx.forEach((_,i)=>{
// ๋์๋จ๋ถ ์
let nx = x
let ny = y
while(1){
nx += dx[i]
ny += dy[i]
if(!board[nx]||!board[nx][ny]||board[nx][ny]==='D'){
let [prev_x,prev_y] = [nx-dx[i],ny-dy[i]]
if(visit_map[prev_x][prev_y]===false){
queue.push([prev_x,prev_y,count+1])
visit_map[prev_x][prev_y]=true
}
break;
}
}
})
}
return min === undefined ? -1 : min
}
'๐Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ๋ก๊ทธ๋๋จธ์ค[JS] > [PCCP ๊ธฐ์ถ๋ฌธ์ ] 3๋ฒ / ์ถฉ๋์ํ ์ฐพ๊ธฐ (0) | 2024.09.11 |
---|---|
ํ๋ก๊ทธ๋๋จธ์ค[JS] > ๊ฑฐ์ค๋ฆ๋ (2) | 2024.09.06 |
ํ๋ก๊ทธ๋๋จธ์ค[JS] > ๊ดํธ ๋ณํ ( 2020 KAKAO BLIND RECRUITMENT ) (0) | 2024.08.24 |
ํ๋ก๊ทธ๋๋จธ์ค[JS] > ์ด๋ชจํฐ์ฝ ํ ์ธํ์ฌ (0) | 2024.08.24 |
ํ๋ก๊ทธ๋๋จธ์ค[JS] > ๋จ์ด๋ณํ (0) | 2024.08.24 |