문제
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음 과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요.
[입력설명]
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다.
[출력설명]
점프의 최소횟수를 구한다. 답은 1이상입니다.
입력예제 1
5 14
출력예제 1
3
입력예제 2
8 3
출력예제 2
5
문제 풀이
코드
- 문제에서 앞으로는 +1, 뒤로는 -1, 앞으로는 +5로 표현할 수 있다.
- 문제에서 직선의 좌표점은 1~10000까지라고 되어있다.
따라서 ch배열과 distance배열은 인덱스가 10,000까지 있어야하기 때문에, length:10001로 잡는다. - 문제풀이 원리는 다음과 같다.
<!--방법1: dis 배열 사용-->
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(s, e){
let answer=0;
let ch=Array.from({length:10001}, ()=>0);
let dis=Array.from({length:10001}, ()=>0);
let queue=[];
ch[s]=1; //출발지점 체크
queue.push(s); //출발지점 push
dis[s]=0; //현수의 출발지점 (0 level)
while(queue.length){
let x=queue.shift();
//세가닥으로 뻗음
//nx는 x에서 한번 더 뻗어간 지점 (dis[x]: 부모노드 x의 거리값)
for(let nx of [x-1, x+1, x+5]){
//목표지점 찾았을 때
if(nx===e) return dis[x]+1; //nx===e인것을 찾으면, 부모노드의 level+1을 하고 while문 종료
//목표지점 찾지 못했을 때
if(nx>0 && nx<=10000 && ch[nx]===0){
ch[nx]=1;
queue.push(nx);
dis[nx]=dis[x]+1;
}
}
}
return answer;
}
console.log(solution(5, 14));
console.log(solution(8, 3));
</script>
</body>
</html>
<!-- 방법2: 레벨에서 뻗어나감-->
<!--
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(s, e){
let answer=0;
let ch=Array.from({length:10001}, ()=>0);
let queue=[];
queue.push(s);
ch[s]=1;
let L=0;
while(queue.length){
let len=queue.length;
for(let i=0; i<len; i++){
let x=queue.shift();
for(let nx of [x-1, x+1, x+5]){
if(nx===e) return L+1;
if(nx>0 && nx<=10000 && ch[nx]===0){
ch[nx]=1;
queue.push(nx);
}
}
}
L++;
}
return answer;
}
console.log(solution(5, 14));
</script>
</body>
</html>
-->
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/18
return 결과값 출력 후, 프로그램 종료