BFS로 풀이

안녕하세요^^

이 문제는 공이 한 방향으로 굴러가다가 벽을 만나면 멈추는 방식으로 이동합니다. 그래서 한 칸씩 이동하면서 distance[다음 정점] = distance[현재 정점] + 1 을 해주는 방식으로는 안됩니다.

아래 입력의 경우 공이 board[1][0]에서 board[3][1]로 이동하는 경로는 [1, 0] - [1, 1] - [1, 2] - [1, 3] - [2, 3] - [3, 3] - [3, 2] - [3, 1]과 같이 7번의 이동으로 도착해야 합니다. 그런데 stance[다음 정점] = distance[현재 정점] + 1과 같이 이동하면 [1, 0]에서 [3, 1]로 가는 최단경로를 [1, 0] - [1, 1] - [2, 1] - [3, 1]로 3번의 이동으로 갈 수 있다고 해법립니다.

구체적인 코드를 봐야 알겠지만 다익스트라와 BFS 2개의 시간복잡도 차이는 크지 않다고 생각합니다.

안녕하세요, 인프런 AI 인턴이에요. 공굴리기 문제에 대한 질문이군요.

강의에서 설명한 대로, 간선의 가중치가 모두 1이라면 BFS를 활용하여 문제를 풀 수 있습니다. 각 정점까지의 최단 거리를 구하는 BFS 방식을 사용하면 됩니다. 각 정점까지의 최단 거리를 저장하는 distance 배열을 사용하여, 현재 정점에서 다음 정점으로 이동할 때마다 distance를 업데이트해주면 됩니다.

다익스트라 알고리즘과 BFS의 시간복잡도에 대해서 설명드리면, 다익스트라 알고리즘은 최단 경로를 구하는 알고리즘으로서, 우선순위 큐를 사용하여 최단 거리를 유지하면서 정점을 선택하는 방식입니다. 이에 반해, BFS는 너비 우선 탐색을 하는 알고리즘이기 때문에 큐를 사용하여 탐색하는 방식입니다.

따라서, 다익스트라 알고리즘은 각 정점을 한 번씩 방문하기 때문에 O(V)의 시간복잡도를 가지고 있고, 간선의 개수에 따라 O(ElogV)까지 소요될 수 있습니다. 반면에 BFS는 인접한 정점을 모두 탐색하기 때문에 각 정점에서 인접한 간선을 한 번씩 방문하는 특성을 가지고 있어서, 간선의 개수에 따라 O(V+E)의 시간복잡도를 가집니다.

따라서, 간선의 개수가 적은 경우에는 양쪽 모두 유사한 성능을 보일 수 있지만, 간선의 개수가 많은 경우에는 다익스트라 알고리즘이 더 효율적이라고 할 수 있습니다.

프로그래밍에서는 일반적으로 간선의 가중치가 모두 동일한 경우에는 BFS를 사용하는 경우가 많습니다. 하지만, 간선의 가중치가 다른 경우에는 다익스트라 알고리즘을 사용해야 정확한 최단거리를 구할 수 있습니다.

효율성 측면에서는 다익스트라 알고리즘이 더 우수한 성능을 보여줄 수 있으므로, 간선 가중치가 다른 경우에는 다익스트라 알고리즘을 고려해보시는 것이 좋습니다.

다른 문의 사항이 있으시면 언제든지 물어보세요!