appl4368   1년 전

안녕하세요. 문제를 풀다 -1, 1 그리고 순간이동의 순서에 대해 의문이 생겨 질문드립니다.

저는 기본적인 bfs코드에서 dx=[-1, 1, 0]으로 선언하고 for문을 돌렸는데요,

입력이 0 27이 주어질 경우 제 코드에서는 4가 출력되어서 오답인데,

dx를 -1, 0, 1로 바꾸면 정답으로 나옵니다.

순간이동만 appendleft로 큐의 앞에 넣어주면 괜찮다고 생각했는데 저 두가지 dx의 차이점을 모르겠습니다.

혹시 아시는 분은 알려주시면 감사하겠습니다~!!

psj_0708   1년 전

해당 칸에 *2로도 도달할 수 있고 +1로도 도달할 수 있는 경우 dx의 순서가 문제가 됩니다.

예를 들어 입력으로 0 2가 주어지면 큐에서 먼저 0을 뽑은 후 visited[1]에 1이 저장될 것이고,

큐에서 1이 뽑혔을 때 dx 배열에서 1이 먼저 있냐 0이 먼저 있냐에 따라 visited[2]에 2 또는 1이 저장되게 됩니다. (물론 정답은 1입니다)

처음 도착했을 때만 visited를 갱신해서 생긴 문제이므로 더 빨리 도착하는 방법이 나오면 다시 갱신해주거나,

아니면 해당 정점을 방문할 때 그것이 무조건 최소 거리가 되도록 알고리즘을 짜야 합니다.

appl4368   1년 전

아 최소거리가 되도록 알고리즘을 짜야 한다는 것을 잊어버렸네요... 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.