반응형
문제풀이
1. 주어진 maps에서 S, L, E의 위치를 탐색합니다.
2. 다익스트라 알고리즘을 활용하여 S -> L, L ->E 까지의 최단시간을 탐색합니다.
3. S -> L, L -> E 모두 도달 가능한 경우, 두 시간을 합친 값을 반환합니다.
JS Code
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
//https://school.programmers.co.kr/learn/courses/30/lessons/159993
function solution(maps) {
var answer = 0;
let start = [0,0];
let end = [0,0];
let lever = [0,0];
// S, L, E 좌표 탐색
maps.map(function(row, i){
let chk = 0;
row.split('').map(function(r, j){
if ( r == 'S' ){
start = [i,j];
chk += 1;
}
if ( r == 'E'){
end = [i,j];
chk += 1;
}
if ( r == 'L'){
lever = [i,j];
chk +=1
}
if ( chk == 3 ){
return ;
}
})
if ( chk ==3 ){
return ;
}
})
// S -> L 시간
let a = dij(maps, start[0], start[1], lever[0], lever[1]);
if ( a == 10001){
return -1;
}
// L -> E 시간
let b = dij(maps, lever[0], lever[1], end[0], end[1]);
if ( b != 10001){
return a+b;
}else {
return -1;
}
}
// (r,c) -> (tr,tc) 걸리는 시간 반환
function dij(maps, r, c, tr, tc){
let chk = Array.from(Array(maps.length), () => Array(maps[0].length).fill(0));
let dist = Array.from(Array(maps.length), () => Array(maps[0].length).fill(10001));
dist[r][c] = 0;
let q = [[r,c]];
while (q.length>0){
let n = q.shift();
if ( n[0]>0 && chk[n[0]-1][n[1]] == 0 && maps[n[0]-1][n[1]] != 'X'){
dist[n[0]-1][n[1]] = Math.min(dist[n[0]][n[1]] + 1)
chk[n[0]-1][n[1]] = 1;
q.push([n[0]-1,n[1]]);
}
if ( n[0]<maps.length-1 && chk[n[0]+1][n[1]] == 0 && maps[n[0]+1][n[1]] != 'X'){
dist[n[0]+1][n[1]] = Math.min(dist[n[0]][n[1]] + 1)
chk[n[0]+1][n[1]] = 1;
q.push([n[0]+1,n[1]]);
}
if ( n[1]>0 && chk[n[0]][n[1]-1] == 0 && maps[n[0]][n[1]-1] != 'X'){
dist[n[0]][n[1]-1] = Math.min(dist[n[0]][n[1]] + 1)
chk[n[0]][n[1]-1] = 1;
q.push([n[0],n[1]-1]);
}
if ( n[1]<maps[0].length-1 && chk[n[0]][n[1]+1] == 0 && maps[n[0]][n[1]+1] != 'X'){
dist[n[0]][n[1]+1] = Math.min(dist[n[0]][n[1]] + 1)
chk[n[0]][n[1]+1] = 1;
q.push([n[0],n[1]+1]);
}
}
return dist[tr][tc]
}
|
cs |
문제 링크
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
반응형
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 바탕화면 정리 JS (0) | 2023.03.05 |
|---|---|
| [프로그래머스] 카드 뭉치 JS (0) | 2023.03.01 |
| [프로그래머스] 대충 만든 자판 JS (0) | 2023.03.01 |
| [프로그래머스] 보석 쇼핑 Python (0) | 2022.03.05 |
| [프로그래머스] 후보키 Python (0) | 2022.03.01 |