https://www.acmicpc.net/problem/1697
백준 1697번 숨바꼭질이다.
역시나 틀렸기 때문에 글을 작성한다.
처음봤을 때는 이게 왜 우선 탐색문제일까 했는데 모든 경우의 수를 생각해 보니까 익숙한 그래프 형태가 나왔다.
1번 연산은 X-1, 2번 연산은 X+1, 3번 연산을 X * 2 이다.
수빈이의 위치에 각각 연산을 적용해서 각각의 경우의 수가 발생한다.
발생된 각각의 경우의 수에 또 각각 세가지 연산을 적용해서 각각의 경우의 수가 발생한다. 이 과정을 동생의 위치인 17이 나올 때 까지 반복한다.
발생한 경우의 수는 모두 Q에 넣는다.
ex) Q = []
경우의 수 : 5, Q = [4,6,10]
경우의 수: 4, Q = [6,10,3,5,8]
경우의 수:6, Q = [10,3,5,8,5,7,12]
.
.
그럼 시간은 어떻게 표현할까?
경우의 수가 분기되는 방식이 5 -> 4/6/10 -> 3/5/10/5/7/12/9/11/20
이런 식으로 분기 되고 각 경우의 수마다 세개의 경우의 수로 분기되기 때문에 3의 제곱의 수로 분기된다. 그러므로 3의 0제곱 -> 3의 1제곱 -> 3의 2제곱 -> 3의 N제곱.... 이런 식으로 나타난다.
예제의 경우에는 17이 경우의 수가 3의 4제곱으로 분기될 때 나왔다.
그러므로 원하는 수 (동생의 위치)가 나올 때의 분기된 경우의 수의 갯수가
3의 몇 제곱인지 구해서 시간으로 표시해주었다.
다음은 코드이다.
//const input = require('fs').readFileSync('./input.txt').toString().trim()
const input = require('fs').readFileSync('/dev/stdin').toString().trim();
let commands = input.split(' ').map((v)=>+v);
[departure, arrival] = commands;
const subtract = (num)=>{
return num-1;
}
const add = (num)=>{
return num + 1;
}
const multiply = (num)=>{
return 2*num;
}
const bfs = (departure,arrival)=>{
let queue = [];
let time = 0;
let result_sub = subtract(departure);
queue.push(result_sub);
let result_add = add(departure);
queue.push(result_add);
let result_mul = multiply(departure);
queue.push(result_mul);
time++;
if([result_sub,result_add,result_mul].includes(arrival)){return time;}
let count = 0;
while(true){
let X = queue.shift();
let result_sub2 = subtract(X);
queue.push(result_sub2);
let result_add2 = add(X);
queue.push(result_add2);
let result_mul2 = multiply(X);
queue.push(result_mul2);
count = count+3;
if(count === Math.pow(3,time)){
time++;
count = 0;
}
if([result_sub2,result_add2,result_mul2].includes(arrival)){
return time;
}
}
}
console.log(bfs(departure,arrival));그리고 틀렸다.. ㅋㅋ
예제로 큰 수를 집어 넣었더니 무한 루프를 돌았다.
다른 사람 블로그에서 정답인 코드를 가져와서 큰 수를 집어 넣어보았다.
예제 입력값으로 '45695 65299' 를 넣어줬더니 출력이 13047로 나왔다.
생각해보니 내가 작성한 코드에서 13047이 나오려면 경우의 수의 갯수가
3의 13047 제곱개가 있어야 했고, 그 많은 수의 갯수를 큐에도 집어 넣어야 했다.
아래는 맞은 코드도 보고 도움도 받아 다시 정리한 내용이다.
몇가지로 나눠서 정리해보았다.
-
왜 bfs인가?
(수직선상 그림, 4개, 초마다.. 5-10-9-18-17 )
힌트에서 알 수 있듯이 최단 거리를 가려면 이러한 경로를 거친다.
하지만 당연히 이것 말고도 무수히 많은 경로가 있고 그 중에서도 가장 최단 거리를 찾는 문제이다.
경우의 수를 그래프로 표현 할 수 있고 최단거리(여기서는 최단시간)를 찾는 문제이므로 BFS를 활용할 수 있다.
-
먼저 한 시도에서 간과한 부분
-
범위 설정: 수빈이와 동생의 위치는 모두 0과 100000 사이에 있다.
수빈이의 위치를 통해서 각각 연산을 해서 나온 위치가 동생의 위치인지 확인해 보는 것이므로 0보다 작거나 100000보다 큰 위치에 대해서는 상관하지 않는다. (큐에 집어 넣을 필요가 없다.) -
중복된 값은 큐에 집어넣지 않기:
중복을 제거해도 되는가?
이미 확인 한 값은 이 전과 똑같은 경우의 수를 생성한다. 그 값은 이미 확인해 본 값들이므로 굳이 확인 할 필요가 없다.
먼저 내가 한 시도에서는 발생된 값의 갯수가 3의 몇 제곱인지, 지수를 시간의 값으로 표현했기 때문에 중복을 제거하면 안되었다. 하지만 그렇게 하면 큐에 들어가는 값의 갯수가 너무 많아지기 때문에 시간이 너무 많이 들었다.
- 시간값 계산해주기
여기서는 두 가지 방법을 작성한다.
첫 번째는 현재의 위치와 시간을 배열에 저장해두고 그 위치에 대해서
1초동안 갈 수 있는 위치로 분기할 때 그 위치와 시간값+1을 큐에 저장하는 것이다. 교수님의 도움을 받았다.
const input = require('fs').readFileSync('./input.txt').toString().trim()
//const input = require('fs').readFileSync('/dev/stdin').toString().trim();
let commands = input.split(' ').map((v)=>+v);
[N, K] = commands;
const subtract = (N)=>{
return N-1;
}
const add = (N)=>{
return N+1;
}
const multiply = (N)=>{
return 2*N;
}
const arr = Array(1000001).fill(0);
const bfs = (departure, arrival)=>{
let time = 0;
arr[departure] = 1; // 방문처리
if(departure === arrival){return time;}
let Q = [[departure,time]];
// 위치와 위치에 가기까지 걸린 시간을 저장해준다.
// 처음위치까지 걸린 시간은 없으므로 시간은 0이다.
while(Q.length){
let X = Q.shift();
let currentPosition = X[0]; //현재 위치
time = X[1]; // 현재 위치까지 걸린 시간
let positions = [subtract(currentPosition),add(currentPosition),multiply(currentPosition)];
//한 위치에서 1초동안 갈 수 있는 모든 위치를 구한다. [4,6,10]
for(let i = 0; i<positions.length; i++){
if(positions[i]>=0 &&
positions[i]<=100000 &&
arr[positions[i]]===0){
//구한 1초 동안 갈 수 있는 위치가
//수직선 상 유효한 값이고 아직 방문하지 않은 값인 경우에
arr[positions[i]] = 1;
Q.push([positions[i],(time+1)]);
// 1초 후에 갈 수 있는 위치와 걸릴 시간을 넣어준다.
if(positions[i]===arrival){
return Q.pop()[1];
}
}
}
}
}
console.log(bfs(N,K));
다음은 두 번째 방법이다.
다음 블로그의 글을 보고 수정했다.
(다른 사람 블로그에서 가져온 맞은코드)
https://velog.io/@ywc8851/%EB%B0%B1%EC%A4%80-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-javascript
const input = require('fs').readFileSync('./input.txt').toString().trim()
//const input = require('fs').readFileSync('/dev/stdin').toString().trim();
let commands = input.split(' ').map((v)=>+v);
[N, K] = commands;
const subtract = (N)=>{
return N-1;
}
const add = (N)=>{
return N+1;
}
const multiply = (N)=>{
return 2*N;
}
const arr = Array(1000001).fill(0);
// 이미 확인한 위치는 다시 확인할 필요가 없다는 것을 전제로 한다.
const bfs = (departure, arrival)=>{
let time = 0;
if(departure === arrival){return time;}
arr[departure] = 1;
let Q = [departure];
time++;
while(Q.length){
let Qlength = Q.length;
// ex = 1,
for(let i = 0; i<Qlength; i++){
let X = Q.shift();
let positions = [subtract(X),add(X),multiply(X)];
for(let j = 0; j<positions.length; j++){
if(positions[j] >= 0 &&
positions[j] <= 100000 &&
arr[positions[j]] === 0
) {
arr[positions[j]] = 1;
Q.push(positions[j]);
if(positions[j] === arrival){
return time;
}
}
}
}
time++;
}
}
console.log(bfs(N,K));
