이렇게 영역을 넓혀가다가 도착지에 제일 먼저 도착했을 당시의 칸 수가 최단 거리가 되는 것이다!
최종 코드 (bfs)
처음 코드 (dfs - 효율성 테스트 미통과)
종혁
구현
좌표에서 상하좌우 이동하는 문제+이동거리까지 구하는 문제는 bfs밖에 생각이 안났음
bfs를 이용하여 상대 팀 진영으로 갈 수 있는지 - 갈 수 있다면 이동거리는 얼마나 되는지를 구해야 함
[0,0]이 담긴 큐에서 시작하여 큐에서 shift() 되어 나온 좌표에서 인접한 좌표 중 막혀있지 않거나 , 인덱스를 넘어가지 않는 좌표들은 모두 큐에 넣으면서, 해당 좌표까지 이동할 수 있는지를 체크
visited 배열을 사용하여 이미 방문했던 좌표를 관리 + 이동시간까지 체크
Ex)[0,0]좌표에서 출발했으면 [0,1] , [1,0] 까지는 이동거리가 1, [0,1]에서 출발하여 [1,1]로 가는 이동거리는 1+1 = 2
코드
재웅
구현
최단거리? BFS(queue)
조건 고려 후 이동, 이동 시마다 Score 계산
맵 범위를 벗어나지 않는 경우
벽(0)이 아닌 경우 길(1)인 경우
목표지점 도달 시의 Score 반환
코드
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
👧🏻
수영
처음에 dfs+스택으로 구현하려고 했다.
다시 풀어볼 예정
👧🏻
정은
문제 보자마자 익숙한 dfs만 떠올랐지 bfs는 전혀 고려해보지 않았다
dfs와 다른 방식이라 신선했다. 다음번엔 최소거리는 두가지 방법을 모두 고려해봐야겠다.
bfs의 개념을 잡고, 구현하는 것에 감을 잡을 수 있는 시간이었다.
👦🏻
종혁
bfs + 이동거리까지 탐색해야 하는 문제
👦🏻
재웅
완탐은 DFS, 최단거리는 BFS로 풀면 된다는 노하우? 고정관념이 있는데 세션 내용을 바탕으로 개선해봐야겠습니다.
전형적인 2차원 배열에서의 최단거리 탐색이라 큰 어려움 없이 해결할 수 있었습니다.
function solution(maps) {
let answer = 1;
let visited = maps;
const n = maps.length - 1;
const m = maps[0].length - 1;
const queue = [[0, 0]];
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
while (queue.length) {
let size = queue.length;
for(let i = 0; i < size; i++) {
let [x, y] = queue.shift();
// 상하좌우 확인
for (let j = 0; j < 4; j++) {
let nx = x + dx[j];
let ny = y + dy[j];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] === 1) {
queue.push([nx, ny]);
visited[nx][ny] = 0;
}
}
}
answer++;
}
// 실패
return -1;
}
function solution(maps) {
var step = 1; //칸 수
let visitedMaps = maps;
const finish = [maps.length-1, maps[0].length-1]; //도착지점
let bfsQueue = [[0,0]];
let next = [[1,0],[-1,0],[0,1],[0,-1]]; //다음 방향을 위해
visitedMaps[0][0] = 2; //지금 지점을 방문표시, 다시 접근하지 않는다.
while (bfsQueue.length) { //가능한 모든 경우의 수(도착지에 도착하면 중간에 종료될 수 있음)
const queueSize = bfsQueue.length; //현재 큐에 들어있는 요소 개수 == 다음 칸으로 갈 수 있는 방법의 수
for (let i=0; i<queueSize; i++) { //다음에 갈 수 있는 칸 수
const [x,y] = bfsQueue.shift(); //dequeue, 현재지점
for (let i=0; i<4; i++){ //동서남북
const nextX = x+next[i][0]; //다음 칸 계산
const nextY = y+next[i][1];
//다음칸이 갈 수 있는 칸이면
if (nextX>=0 && nextY>=0 && nextX<=finish[0] && nextY<=finish[1] && visitedMaps[nextX][nextY] != 2 && visitedMaps[nextX][nextY] != 0) {
if (nextX===finish[0] && nextY===finish[1]) { //도착하면
return step+1;
}
//도착하지 않았으면 다음 칸을 방문 표시하고 큐에 추가
visitedMaps[nextX][nextY] = 2;
bfsQueue.push([nextX,nextY]);
}
}
}
step++; //칸 증가
}
return -1; //return되지 않았다면, 도착하지 않았다는 것
}
function solution(maps) {
var answer = Infinity;
const finish = [maps.length-1, maps[0].length-1];
function dfs(i,j,count) {
if (i < 0 || i > finish[0] || j < 0 || j > finish[1] || maps[i][j] === 0 || maps[i][j] === 2) {
return;
} //범위 밖 or 갔다온 곳이라면 이전으로 돌아감
if (i === finish[0] && j === finish[1]) { //도착
answer = Math.min(answer, count);
return;
}
maps[i][j] = 2; //흔적 표시
dfs(i+1,j,count+1);
dfs(i,j+1,count+1);
dfs(i-1,j,count+1);
dfs(i,j-1,count+1);
maps[i][j] = 1; //흔적 표시 해제
}
dfs(0,0,1);
return answer === Infinity ? -1 : answer;
}
