[ 해결 방법 ]기본적인 BFS문제인 것 같다. 현재 위치에서 위또는 아래 방향으로 BFS돌리면 된다. [ 내 코드 ]#include #include using namespace std; struct info{ int floor, cnt;};int F, S, G, U, D;int visit[1000002];int dir[2] = { 1, -1 };queue q; int main(){ cin >> F >> S >> G >> U >> D; dir[0] *= U; dir[1] *= D; q.push(info{ S, 1 }); visit[S] = 1; info cur, next; while (!q.empty()) { cur = q.front(); q.pop(); for (int i = 0; i F || next..
[ 풀이 방법 ]토큰이란걸 만들었다. 모든 토큰의 시작점은 트리의 단말노드이다. 토큰에는 현재 위치, 이전 위치, 총 이동거리의 정보를 포함하고 있다. 이 토큰을 큐에 넣고 하나씩 빼면서 현재 위치에서 이동할 수 있는 모든 방향으로 퍼지게 만들었다(BFS 방법). 이 때, 왔던 길로 다시 못가게 하기 위해서 토큰에 이전 위치를 저장했다. 이제 가려고하는 위치와 이전 위치가 같다면? 왔던길로 다시 돌아가는 거니까 못가게 막았다. 그리고 예외 상황이 문제를 짜증나게 만들었는데, 첫번째는 지름이 단말-단말 뿐만 아니라 단말-루트도 가능하다. 루트가 자식노드를 하나만 갖고 있으면 이런 경우가 가능하다. 두번째는 단말노드를 큐에 넣으면 안된다. 1만개쯤의 노드가 있다면 단말노드는 수천개쯤 된다. 메모리가 뻑날 수..