Be a developer

bfs는 모든 가중치가 1일 때 가능하다. 앞서 풀었던 숨바꼭질 문제는 수빈이가 이동할 때 모두 1초가 걸렸기 때문에 가능했다. 하지만 이번 문제는 0초에 이동할 수 있어서 가중치가 0인 경우가 있다. 원래 bfs는 queue에 넣는 건데, 다 가중치가 1이기 때문에 거리가 1일 때, 거리가 2일 때 차곡차곡 쌓인다. 하지만 가중치가 다르면 꺼냈을 때 값이 뒤죽박죽이 된다. 이럴 경우에 queue를 여러 개 사용해서 푼다. 즉, 0초 일 때 넣을 queue와 1초 일 때 넣을 queue 총 2개를 사용해서 문제를 푼다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #..