Tree traversal(그래프 순회)에 대해 정리한지 얼마나 됐다고 다까먹었다. 사실 정리고 뭐고 하나도 이해를 못한것이 분명하다. 이번엔 꼭 마스터를 하리라. 그리고 문제도 다 완전 나의 힘으로만 풀 것이다!
바킹독님의 강의를 정리했다!
🔍 알고리즘 설명
BFS(Breath First Search)
다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
강의에서 설명한 내용 중, BFS를 한방에 이해하는 예시로
그림판의 "페인트" 기능을 설명해주셨다.
우리가 채우고 싶은 특정 부분을 클릭하면 모든 픽셀을 방문하며, 클릭한 픽셀과 동일한 색은 칠해버리는 것이 BFS를 참 잘 설명한다고 생각했다.
이전에도 설명했지만, BFS는 간선과 정점으로 이루어진 그래프이다.
🔍 예시
위에서 말한 퍼진다는 것을 기억하고서 순서를 따라가보자!
- 시작하는 칸을 큐에 넣고 방문했다는 표시를 함.
- 큐에서 원소를 꺼내고, 그 칸의 상하좌우로 인접한 칸에 대해 다음 과정을 수행한다.
- 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다.
- 큐가 빌때까지 2, 3번을 반복한다.
모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때, O(N)이다.갑자기 확 이해되지 않는가??!!!
큐의 성질을 활용해서 방문했다면+조건에 맞다면 방문하고 큐에 넣고
front에서 하나 빼고, 상하좌우 조건에 맞는지 검사하고 조건에 맞으면 큐에 넣고!
이렇게 하면 조건에 맞는 모든 노드들을 방문 가능하다!
‼️주의사항
- 시작점에 방문했다는 표시를 남겨야 한다.
- 큐에 넣을 때 방문했다는 표시를 해야 한다.
- 이웃한 원소가 범위를 벗어났는지에 대한 체크를 해야한다.
🔍 응용
BOJ 2178번 미로탐색 👨🏻🏫
다차원 배열에서의 거리 측정 문제
- 미로의 좌측 상단으로부터 우측 하단으로 가는 최단 경로의 길이를 찾는 문제
- BFS를 이용하면 시작 점으로부터 이어지는 모든 점으로부터의 최단 경로를 찾을 수 있음
🤯의문점: BFS는 단순히 모든 경로를 방문하는 것 아닌가? 순서를 어떻게 지정하는거지
바로 이런 방식으로 지정해주면 된다!!
방문여부를 true, false로 저장하는 방식이 아닌 숫자로 지정해주는 방식을 통해 시작점으로부터의 거리를 명시해주면 최단 경로를 찾는 것이 가능하다
dist배열을 만들고, -1로 초기화해주면 visited 테이블을 만들 필요가 없다!BOJ 7576번 토마토 👨🏻🏫
시작점이 여러개인 BFS
- 토마토가 다 익기까지 얼마만큼의 시간이 걸리는지 판단하는 문제
- 모든 익지 않은 토마토와 얼마나 가까운 곳에 익은 토마토가 있는지 판단
- 미로처럼 시작 부분이 하나만 존재하는 것이 아니라 여러개가 존재 가능!(익은 토마토가 여러개일 수 있음.)
🤔 그러면 모든 익은 토마토에 대해 BFS를 수행하는 방법으로 하면 안되나?
➡️ 시간복잡도가 제곱수로 늘어나버림! 너무 비효율적이라 해당 방법은 기각!일단 그래도 시작점이 여러개인 BFS를 돌린다고 생각하면 그래도 실마리가 보인다.
모든 시작점을 큐에 넣고 BFS를 돌리게 되면 문제를 풀 수 있다!
🤯의문점: 큐에 그냥 익은 토마토들을 다 넣어버린다고!? 그럼 이후로 진행할 때 꼬이는거 아닌가?!
좀 바보같은 질문일 수는 있지만 일단 나의 경우엔 바로 이해가 가지 않았다.
큐에 그냥 익은 토마토들을 다 넣어버려도 상관없는 이유는 FIFO 성질 때문이다!
처음에 들어간 토마토(이미 익어있는 토마토)부터 확인하며,
한 구역에서만 판단하는게 아닌 여러 구역에서 건너뛰어가며 확인이 가능하다!- 익은 토마토를 queue에 넣고, 익지 않은 토마토는 dist값을 -1로 초기화한다.
- BFS를 수행한다.
- 결과적으로 max값을 찾고, 익지 않은 토마토가 있는지도 꼭 확인해주어야 한다.
BOJ 4179 불! 👨🏻🏫
BFS를 두번 사용해야 하는 문제
지훈이가 나가는 길도 찾아줘야되고, 불이 어떻게 퍼지는지도 고려해야 하는 문제
➡️ 불의 퍼지는 시간을 먼저 고려하고, 이후로 지훈이의 탈출을 도와주자!
- 불이 퍼지는데 걸리는 시간 배열을 만들고, 지훈이가 이동하는 시간 배열도 만들어야 한다.
- 두 배열을 비교해서, 지훈이가 계속 이동을 한다고 가정하고 범위를 벗어났을 때, 그 첫 시간값을 출력하면 된다!
🤯의문점: 왜 첫 시간값을 출력하지..?
큐에는 가까운 순서대로 저장되게 된다!
따라서 처음 나오는 값이 앞으로 나오는 값들 중, 가장 작은 값이라고 할 수 있다.다만 이 문제는 불의 전파는 지훈이의 영향을 받지 않고, 지훈이만 영향을 받음.
그렇기에 불을 먼저 전파시키고 지훈이의 BFS를 수행한것임.
🤔 그렇다면 만약 둘 다 영향을 받는 상황이라면?
이렇게 되면 어느 하나를 끝까지 먼저 전파시킨다는게 불가능함.
시간순으로 두개를 전부 다 진행시켜야 한다!BOJ 1697 숨바꼭질 👨🏻🏫
BFS에서 움직이는 범위가 다른 문제!
별로 이번 문제에 있어서는 많은 설명이 필요 없어 보인다.
다만 지금까지는 상하좌우로만 이동했지만, 이번에는 조금 다른 형태도 포함해서 이동한다고 보면 된다. 로직은 동일하다!
‼️ 하지만 추가적인 고려 사항이 존재한다.
범위를 항상 체크해주자!
이번 문제에서는 범위를 벗어나면 안된다는 말이 없고, 벗어나도 문제가 없는 문제이다!
최대 범위가 10만을 넘어갈 수 있다는 말이다.
이런식으로 문제를 꼼꼼히 읽는 기술이 필요하다.
출처
.jpeg)