https://www.acmicpc.net/problem/1697
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제입력 :5 17
예제 출력 : 4
처음 접근
0부터 100,000까지의 일차원 좌표에서 수빈이와 동생의 좌표가 주어진다.
수빈이는 x+1, x-1, 2x로 이동할 수 있고, 이때 가장 빠르게 찾는 시간을 출력한다.
가장 빠른 최단경로를 찾는 것이기 때문에 BFS를 사용하고,
이전에 이차원 좌표로 왼쪽, 위, 오른쪽, 아래로 이동하는 경우의 수를 통해 최단경로를 찾았다면
이번 문제는 x+1,x-1,2x를 통해 visited 방문 여부를 확인 후에 경로를 찾으면 될것같다.
걸린 부분
최단경로를 계산하는 부분에서 뭐가 정답이 될지 내가 어떻게알지..? x2를 먼저 해주어야하나? 라는 잘못된 생각을 잠깐 했었던 것 같다. 최적의 답을 구하는 것을 고민하는 그리디 알고리즘 구현이 아니라 모든경우의 수를 계산하며 답을 구하는 브루트포스의 접근 방식중 bfs, dfs를 사용하는 문제라는것을 인지하자.
count를 어떻게 계산할지에 대한 로직을 해결하느라 시간을 많이 잡아먹었다.
좌표에 해당하는 depth를 어떻게 계산해줄지 생각을 하는게 이번 문제의 핵심이었다고 생각한다.
function bfs(x,y)
{
let visited = {}
//현재 좌표와 depth를 선언
let needVisit = [N]
let count = 0
while(needVisit.length>0)
{
console.log(count)
let currentVertex = needVisit.shift()
//수빈이가 동생의 좌표라면
if(currentVertex === y)
{
//depth를 출력 , depth가 결국 시간이 됨
return count;
break;
}
let changedVertex;
//+1,-1,곱하기 2의 경우의 수 중 좌표 조건을 만족하고 방문을 하지 않았다면 넣고 bfs를 돌리기
[currentVertex-1,currentVertex+1,currentVertex*2].forEach(vertex=>{
if(vertex >=0 && vertex <= 100000 && visited[vertex] != true)
{
//그 노드를 방문했다고 초기화
visited[vertex] = true
//방문할 노드에 추가
needVisit.push(vertex)
}
})
count++;
}
}
이런식으로 depth를 계산하는 로직을 짜고 count를 출력해보았다.
결과
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
처음엔 이런식으로 while문을 벗어날때마다 count를 더해주려고 했지만 while문이 돌아간 횟수를 그대로 출력해줘서 다른 방식으로 선언을 해줘야겠다고 생각을했다.
일반적인 count ++로는 depth가 계산이 안되므로 needVisit에 [좌표,depth] 자체를 선언하면 반복문을 몇번 도는 것과는 상관없이 좌표에 대한 depth를 각각 계산할 수 있다.
제출한 정답 코드
const fs = require('fs')
// const input = fs.readFileSync('../text.txt').toString().split(' ').map(item=>+item)
const input = fs.readFileSync('dev/stdin').toString().split(' ').map(item=>+item)
const [N,K] = input
console.log(bfs(N,K))
function bfs(x,y)
{
let visited = {}
//현재 좌표와 depth를 선언
let needVisit = [[N,0]]
while(needVisit.length>0)
{
let [currentVertex,depth] = needVisit.shift()
//수빈이가 동생의 좌표라면
if(currentVertex === y)
{
//depth를 출력 , depth가 결국 시간이 됨
return depth
break;
}
let changedVertex;
//+1,-1,곱하기 2의 경우의 수 중 좌표 조건을 만족하고 방문을 하지 않았다면 넣고 bfs를 돌리기
[currentVertex-1,currentVertex+1,currentVertex*2].forEach(vertex=>{
if(vertex >=0 && vertex <= 100000 && visited[vertex] != true)
{
//그 노드를 방문했다고 초기화
visited[vertex] = true
//방문할 노드에 추가
needVisit.push([vertex,depth+1])
}
})
}
}이렇게 되면 최단경로를 계산할때까지의 좌표를 만나기전에 depth가 커지게 되어도, 결국 최단경로에 대응하는 depth를 계산할 수 있게된다.
정리
1.최단경로를 구하는 문제는 BFS를 사용할 생각을하자.
2.depth를 구하는 문제는 일반적인 count++로 계산하기가 복잡하고 어려워보인다.
needVisit = [탐색하는 vertex] 이렇게만 선언하지 말고
needVisit = [탐색하는 vertex, depth] 로 선언해서
needVisit.push([vertex,depth+1])를 통해 depth를 구하는 방식을 기억하자.
3.그 외 다른 방식들은 일반적인 bfs 구현 후 이동할 수 있는 경우의 수를 찾으며 조건에 만족하는것들을 push하는 방식으로 다른 문제들과 비슷한 결을 보인다.
4. bfs, dfs문제인것을 인지하고 풀때 저 정답을 빠르게 찾는 로직을 어떻게 짜지? 라는 그리디알고리즘 접근 방식보단 브루트포스로 경우의 수를 다 계산해보고, 그중에 답을 찾는다. 라는 생각으로 문제를 푸는게 아직까지 겪은 bfs dfs문제들의 좋은 접근방식이었다.
끝!
