https://www.acmicpc.net/problem/13913
해당 문제는 숨바꼭질 1 문제에서 추가로 이동한 경로까지 구하는 문제이다.
문제를 풀기 전에 이전에 풀었던 숨바꼭질 1 문제를 다시 살펴보자.
https://www.acmicpc.net/problem/1697
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])
}
})
}
}처음접근
해당 문제에선 needVisit에서 수빈이가 동생의 좌표로 이동을 했다면(currentVertex === y)
depth를 구하고 반복문을 종료하는 방식으로 문제를 풀어나갔다.
이번 문제에선 최단 경로까지 가는 모든 경우의 수를 계산하고, 이동한 좌표를 출력해보기로 생각을 했다.
생각한 변형 방식 : 경로를 탐색하는 route를 needVisit에 추가하자 (완전탐색방식)
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).join('\n'))
function bfs(x,y)
{
let visited = {}
//현재 좌표와 depth를 선언
let needVisit = [[N,[N],0]]
while(needVisit.length>0)
{
let [currentVertex,route,depth] = needVisit.shift()
//수빈이가 동생의 좌표라면
if(currentVertex === y)
{
//depth를 출력 , depth가 결국 시간이 됨
return [depth,route.join(' ')]
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,[...route,vertex],depth+1])
}
})
}
}완전탐색으로 각 좌표에 대한 모든 경로를 needVisit.push([vertex,[...route,vertex],depth+1]) 를통해 구해줬다.
그 후에 수빈이가 동생의 좌표까지 가게 되면 ( if(currentVertex === y) ) depth와 추가해준 경로를 출력하여 답을 구했다.
4
5 4 8 16 17
답은 잘 나오지만..
이렇게하니까
메모리 초과가 난다. needVisit에 너무 많은 경로를 저장하게 되어서 발생하는 문제같았고, 탐색하는 모든 경로를 저장하는게 아닌 정답의 경로만 출력하는 방식을 생각해야했다.
수정된 방식
경로를 일일이 다 넣어주지 말고, path라는 배열을 지정해준뒤 -1,+1, x2로 좌표를 이동할때마다 path에 해당 좌표에 도착하기전 어떤 좌표에서 왔는지를 넣어준다.
path에 이전에 탐색한 좌표를 넣게되면 각 좌표가 이전에 어떤 노드를 거쳤는지 확인할 수 있다.
이런 방식으로 path를 채우면 depth가 낮은 순서대로 path의 배열이 채워지게 되고, visited[vertex]≠true를 통해서 이전에 업데이트 된 path는 다시 업데이트 되지 않게되며 최단경로를 보장할 수 있게된다.
그 뒤에 도착지 (17)에서부터 시작해서
for(let i = 0;i<depth;i++)
{
array.push(path[array[i]])
}
연결된 노드들을 array 배열에 push하고, 시작노드부터 출력해야하기 때문에 reverse를 통해 출력해주었다.
정답코드
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
const path = Array.from({ length: 100000 }, () => 0);
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])
path[vertex] = currentVertex
}
})
}
}
let depth = bfs(N,K)
let array = [K]
for(let i = 0;i<depth;i++)
{
array.push(path[array[i]])
}
console.log(depth)
console.log(array.reverse().join(' '))정리
최단경로의 정확한 이동 경로를 구할땐 탐색한 모든 노드들의 경로를 구하는 완전탐색 방법을 사용은 피하자(메모리 초과가 발생함)
이때 이전에 탐색한 좌표를 현재 탐색노드에 대응해주는 대응해주는 방식을 사용하면 어디서 오게 된 노드인지 알 수 있어 총 이동 경로를 구할 수 있다. index(현재탐색노드)에 이전 탐색노드를 대응해주는 방식
끝 !
