시작점에서 일반적인 BFS를 돌리면 도착 경우의 수가 여러가지가 나오더라도 처음 방문한 것만 방문한 걸로 간주해서 틀리게 나와서, 중복 방문을 허용하는 방법을 생각하다가, 예를 들어 5 17로 가는 경로가 있다고 하면, 5 4 8 16 17 이 있고 5 10 9 18 17이 존재하는데
else if (visited[a] == visited[index] + 1) { q.push(a); }
여기에 visited[a] == visited[index] + 1을 넣어서, 어느 경로로든 목적지에 먼저 도착한 것은 다시 방문 표시를 하지는 않되, 목적지보다 한 단계 낮은 높이에서 목적지에 도달하려고 -1, 1, *2를 시도할 때 찾게 되면 큐에 넣어서 목적지가 더 출력되도록 하고 그 출력 횟수를 세서 코드를 수정했더니 맞았습니다
그런데 이렇게 하면 코드 내에서는 출발지 = 목적지일 때 반영이 되지 않아서 출발지와 목적지가 다른 경우에만 이를 사용하도록 했는데, 생각해보니 이렇게 하면 뭔가 의도에 어긋난 거 같아서 맞긴 했지만 다시 생각해보는 중입니다....
codingismylife 1년 전
시작점에서 일반적인 BFS를 돌리면 도착 경우의 수가 여러가지가 나오더라도 처음 방문한 것만 방문한 걸로 간주해서 틀리게 나와서, 중복 방문을 허용하는 방법을 생각하다가, 예를 들어 5 17로 가는 경로가 있다고 하면, 5 4 8 16 17 이 있고 5 10 9 18 17이 존재하는데
if (visited[a] == 0)
{
visited[a] = visited[index] + 1;
q.push(a);
}
else if (visited[a] == visited[index] + 1)
{
q.push(a);
}
여기에 visited[a] == visited[index] + 1을 넣어서, 어느 경로로든 목적지에 먼저 도착한 것은 다시 방문 표시를 하지는 않되, 목적지보다 한 단계 낮은 높이에서 목적지에 도달하려고 -1, 1, *2를 시도할 때 찾게 되면 큐에 넣어서 목적지가 더 출력되도록 하고 그 출력 횟수를 세서 코드를 수정했더니 맞았습니다
그런데 이렇게 하면 코드 내에서는 출발지 = 목적지일 때 반영이 되지 않아서 출발지와 목적지가 다른 경우에만 이를 사용하도록 했는데, 생각해보니 이렇게 하면 뭔가 의도에 어긋난 거 같아서 맞긴 했지만 다시 생각해보는 중입니다....