BFS
다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
- 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
- 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
- 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
- 큐가 빌 때 까지 2번을 반복
모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)
자주 하는 실수
- 시작점에 방문했다는 표시를 남기지 않는다.
- 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남겼다.
- 이웃한 원소가 범위르 벗어났는지에 대해 체크를 잘못했다.
응용 문제
1. 거리 측정
미로 탐색 같은 문제는 도착 지점 까지 최소칸을 구했던 것 같은데,
코드를 짰을 때 상하좌우로 방문하고 방문한지점에 거리를 표시를 하면서 했었다. 큐에 들어오는것은 먼저 나가기 때문에 최소 지점을 구할 때는 각 방문한 지점에 거리를 표시하면 된다.
2. 시작점이 여러 개일 때
이 문제도 어렵지 않게 풀었던 것 같다.
그냥 시적점을 큐에 먼저 넣고 똑같이 BFS를 진행시키면 된다.
추가로 BFS에 쌓이는 형태는 반드시 거리순이다.
3. 시작점이 두 종류일 때
이 문제는 지훈이와 불을 피해 도착 지점까지 가는 문제인데, 불과 지훈이를 각각 BFS를 돌려서 풀면 된다. 먼저 불의 시간을 BFS를 돌리고 방문한 칸에 불의 시간을 표시하고 지훈이가 방문할 때 시간과 불의 시간을 비교하면서 진행하면 된다.
4. 1차원에서의 BFS
이 문제는 정확히 기억이 안나지만 시작점을 두고 거기에 대해 bfs를 진행했다.
x+1, x-1, x*2 로 한칸 앞 한칸 뒤 2칸 순간이동? 이런 느낌이었던듯
예전에 bfs 문제를 많이 풀었다. 저번에도 이 강의를 봤지만 다시 한번 풀어보는 시간을 가지고 완강 후 나머지 문제도 풀어야겠다
기록하기