90번 심바문제 질문있습니다.

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

90. 라이언 킹 심바(BFS활용)

작성

270

69 ~70 번째 줄인

while (!Q.empty()) { Q.pop(); }

res = tmp.dis;

}

이 부분이 이해가 안됩니다. 왜 큐를 제거를 하는지 이전에 다 없어지지 않았나요? 그리고 dis를 하는이유도 궁금합니다. z로 설정을 다하셨는데 왜 갑자기 이렇게 나오는지....

c++코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

심바가 시작위치에서 가장 가까이에 있는 토끼를 찾아 잡아먹는데 그러기 위해서는 심바의 시작위치를 큐에 최초로 넣고 BFS 탐색으로 심바의 시작위치에서 가장 가까이에 있는 토기를 잡아먹습니다. 그리고 두 번째 잡아먹을 토끼를 찾는데 이때 심바는 첫 번째 잡아먹었던 토끼가 있었던 곳에 심바가 있는 상황입니다. 그래서 두 번째 잡아먹을 토끼는 현재 심바의 위치(첫번째 잡아먹은 토끼의 위치)에서 가장 가까운 토끼가 두 번째로 잡아먹을 토끼입니다. 그래서 큐를 다 비우고 현재 심바의 위치(첫번째 잡아먹은 토끼의 위치)를 빈큐에 최초로 넣고 이 지점부터 BFS로 가장 가까운 토끼(두 번째로 잡아먹을 토끼)를 찾는 것입니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴이에요. 90번 심바 문제에 대해 궁금하신 내용에 대해 답변드리겠습니다.

해당 코드에서 while (!Q.empty()) { Q.pop(); } 부분은 큐(Q)가 비어있을 때까지 큐를 계속해서 비워주는 역할을 합니다. 큐를 비워주는 이유는, 다음에 새로운 값을 찾아서 큐에 넣기 위해서입니다. 큐에는 방문해야 할 위치를 순서대로 저장하는 역할을 하고 있습니다.

이전에 큐에 있는 값은 목적지에 도달할 때까지 계속해서 큐에 넣어야 하기 때문에 큐를 비우지 않아요. 매번 큐에는 새로운 위치를 넣고 이동하기 때문에 큐 안에 이전에 저장된 값들은 필요하지 않게 되죠.

res = tmp.dis;는 res 변수에 tmp.dis 값을 할당하는 부분입니다. 이 코드는 현재 위치(tmp)에서 목적지까지의 최단 거리(tmp.dis)를 res 변수에 저장하는 역할을 합니다.

z로 설정이 되어 있을 때 목적지에 도달하는 경우, 그 때의 최단 거리(tmp.dis)를 res 변수에 저장하는 거에요.

이런 식으로 코드가 실행되며 목적지까지의 최단 거리를 구하게 됩니다.

해당 내용이 이해되셨나요? 추가적인 질문이 있으면 언제든지 물어보세요. 좋은 하루 되세요!

인프런 커뮤니티 질문&답변

90번 심바문제 질문있습니다.