Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- 문자열
- DP
- 너비 우선 탐색
- 깊이 우선 탐색
- Python
- level3
- Lv. 0
- 자바스크립트
- 메모이제이션
- level 3
- Stack
- dfs
- javascript
- 프로그래머스
- programmers
- SQL 고득점 KIT
- 브루트포스
- softeer
- 소프티어
- C언어
- Lv. 1
- Lv. 3
- 파이썬
- bfs
- 스택
- Java
- Lv. 2
- Dynamic Programming
- group by
- 다이나믹프로그래밍
Archives
- Today
- Total
몸과 마음이 건전한 SW 개발자
프로그래머스 [Lv. 2] 게임 맵 최단거리 {언어 : JavaScript} 본문
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/1844
정답 코드
function solution(maps) {
const n = maps.length;
const m = maps[0].length;
const er = n - 1;
const ec = m - 1;
const dr = [1, 0, -1, 0];
const dc = [0, 1, 0, -1];
const isValid = (nr, nc) => {
return 0 <= nr && nr < n && 0 <= nc && nc < m;
};
let V = Array(n).fill().map(() => Array(m).fill().map(() => 0))
const bfs = () => {
const q = [[0, 0]];
maps[0][0] = 0;
while (q.length) {
const [r, c] = q.shift();
for (let d = 0; d < 4; d++) {
const nr = r + dr[d];
const nc = c + dc[d];
if (isValid(nr, nc) && maps[nr][nc] == 1 && V[nr][nc] == 0) {
V[nr][nc] += V[r][c] + 1;
q.push([nr, nc])
}
}
}
}
V[0][0] = 1;
bfs();
const minLen = V[er][ec];
const answer = minLen ? minLen : -1;
return answer;
}
풀이 방법
- visited 배열을 만들었는데 안 만들어도 풀 수 있다.
- 1인 길을 따라간다.
- 길을 따라가면서 거리를 누적한다.
- 최적 경로가 0이라면 도달 못했으므로 -1
느낀점
- bfs와 dfs의 차이를 알면 풀기 쉬운 문제
'알고리즘' 카테고리의 다른 글
프로그래머스 [Lv. 3] 여행경로 {언어 : JavaScript} (0) | 2024.03.19 |
---|---|
프로그래머스 [Lv. 3] 아이템 줍기 {언어 : JavaScript} (0) | 2024.03.19 |
프로그래머스 [Lv. 2] 타겟 넘버 {언어 : JavaScript} (0) | 2024.03.18 |
프로그래머스 [Lv. 2] 전력망을 둘로 나누기 {언어 : JavaScript} (0) | 2024.03.17 |
프로그래머스 [Lv. 2] 피로도 {언어 : JavaScript} (0) | 2024.03.15 |