우선 최단거리를 구하는 것이기 때문에 BFS를 이용하기로 했다.
- queue를 하나 만들고 0,0 초기값을 넣는다.
- 큐가 요소가 없어질때까지 아래과정 반복
-> x,y = queue에서 뽑음
이 뽑은 x,y에 앞,뒤,오른쪽,왼쪽을 움직이면서 아래를 체크한다.
1) x,y가 좌표를 나가지 않는가?
2) 지나갈 수 있는 길인가?
-> 이를 통과하면 queue에 x,y를 넣고 지나간 것으로 벽으로 만듬.- 이 행위들을 반복할때마다 count++를 해준다.
- 만약 이 행위를 반복하다 목표지점에 도달하면 ++count를 리턴
function solution(maps) {
if(maps===[1]){return 1;}
var queue = [[0,0]];
var moveX = [-1,1,0,0];
var moveY = [0,0,-1,1];
var count =1;
while(queue.length>0){
var queLen = queue.length;
for(var q = 0; q<queLen;q++){
let [x,y] = queue.shift();
for(var i =0;i<4;i++){
var newX = x + moveX[i];
var newY = y + moveY[i];
if(newX===maps.length-1&&newY===maps[i].length-1) return ++count;
if(newX>=0&&newY>=0&&newX<maps.length&&newY<maps[0].length&&maps[newX][newY]===1){
queue.push([newX,newY]);
maps[newX][newY] = 0;
}
}
}
count++;
}
return -1;
}
특정 케이스에서 런타임에러, 시간 초과가 발생했다. 왜 이런걸까.... 뭐지
function solution(maps) {
if(maps===[1]){return 1;}
var visit = [];
var queue = [[0,0]];
var moveX = [-1,1,0,0];
var moveY = [0,0,-1,1];
var count =1;
if(maps[maps.length - 1][maps[0].length - 2] === 0 && maps[maps.length - 2][maps[0].length - 1] === 0) return -1;
while(queue.length>0){
var queLen = queue.length;
for(var q = 0; q<queLen;q++){
let [x,y] = queue.shift();
for(var i =0;i<4;i++){
var newX = x + moveX[i];
var newY = y + moveY[i];
if(newX===maps[0].length-1&&newY===maps.length-1) return ++count;
if(newX>=0&&newY>=0&&newX<maps[0].length&&newY<maps.length&&maps[newY][newX]===1){
queue.push([newX,newY]);
maps[newY][newX] = 0;
}
}
}
count++;
}
return -1;
}
문제를 천천히 읽어보니 X,Y값에 대한 배치 문제가 있었다... 문제를 좀 더 집중력 있게 풀어야겠다...ㅠㅠ
문제를 해결하기 위해 끈기있게 고민하시고 결국 푸셨군요! 멋지네요 👍