2023 04 17

BFS

• BFS탐색을 통해 다음 방문한 곳을 하나의 큐를 더 만들어 저장하면, 이 곳들을 새로운 시작점으로 정하여 탐색이 가능함(빙하)
• 갈 수 있는 곳을 세는 것은 방문할 때마다 방문한 위치의 수를 증가시킬 수도 있지만, bfs 완료 후에 방문한 지점들을 세어주는 것도 가능
• 시작점으로부터 최단거리를 거리를 저장할 step배열을 생성, 다음방문할 위치에 시적점으로부터 현재위치까지의 최단거리값 + 1을 해준다.
• 여러 시작점을 한 번에 넣고 bfs를 진행해서 갈 수 있는 서로 다른 곳의 수를 세는 것이 가능한 이유는 1번 2번 시작점이 존재하는 경우, 1번이 방문하는 곳을 2번이 중복해서 방문하지 않기 때문이다.
• 여러 시작점을 한 번에 넣고 bfs를 진행하여서 각 시잠점으로부터 목적지까지의 최단거리를 구할 수 있다.
  • (시작점과 목적지가 주어졌을 때 무조건 시작점에서 시작하는 것이 아니고 목적지에서 시작해서 시작점으로 도달하는 방법도 고려할 수 있음, 비를 피하기)