0x09 BFS
0x00 알고리즘 설명
BFS (Breadth First Search) : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘
0x01 예시 (Flood Fill)
- 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
- 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
- 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
- 큐가 빌 때까지 2번을 반복
모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)
STL pair (utility)
#include <bits/stdc++.h>
using namespace std;
int main(void){
pair<int,int> t1 = make_pair(10, 13);
pair<int,int> t2 = {4, 6}; // C++11 이상
cout << t2.first << ' ' << t2.second << '\n'; // 4 6
if(t2 < t1) cout << "t2 < t1"; // t2 < t1
}→ pair에는 미리 대소관계가 설정되어 있음. 첫번째값 먼저 비교 후 두번째 비교
BFS 코드
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{{1,1,1,0,1,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0,0},
{1,1,1,0,1,0,0,0,0,0},
{1,1,0,0,1,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
queue<pair<int,int> > Q;
vis[0][0] = 1; // (0, 0)을 방문했다고 명시
Q.push({0,0}); // 큐에 시작점인 (0, 0)을 삽입.
while(!Q.empty()){
pair<int,int> cur = Q.front(); Q.pop();
cout << '(' << cur.X << ", " << cur.Y << ") -> ";
for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
int nx= cur.X + dx[dir];
int ny= cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
Q.push({nx,ny});
}
}
}자주하는 실수
- 시작점에 방문했다는 표시를 남기지 않는다.
- 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남겼다.
- 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.
BOJ 1926번 : 그림
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[502][502];
bool vis[502][502];
int n, m;
int dx[4] = {1, 0 ,-1, 0};
int dy[4] = {0, 1, 0, -1};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin >> board[i][j];
int num = 0; // 그림의 수
int mx = 0; // 그림의 최댓값
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(vis[i][j] || board[i][j]= 0) continue;
num++;
queue<pair<int, int> > Q;
vis[i][j] = 1;
Q.push(make_pair(i, j));
int buffer = 0;
while(!Q.empty()) {
pair<int, int> cur = Q.front();
Q.pop();
buffer++;
for(int dir=0; dir<4; dir++) {
int nx= cur.X + dx[dir];
int ny= cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
Q.push(make_pair(nx, ny));
}
}
mx = max(mx, buffer);
}
}
cout << num << "\n" << mx << "\n";
}→ 그림의 최대 크기와 개수를 세는 방법 생각하면 간단하게 구현
0x02 응용1 - 거리 측정
BOJ 2178번 : 미로 탐색
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[102];
int dist[102][102];
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=0; i<n; i++) cin >> board[i];
for(int i=0; i<n; i++) fill(dist[i], dist[i]+m, -1);
queue<pair<int, int> > Q;
Q.push(make_pair(0,0));
dist[0][0] = 0;
while(!Q.empty()) {
pair<int, int> cur = Q.front();
Q.pop();
for(int i=0; i<4; i++) {
int nx= cur.X + dx[i];
int ny= cur.Y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue;
dist[nx][ny] = dist[cur.X][cur.Y]+1;
Q.push(make_pair(nx, ny));
}
}
cout << dist[n-1][m-1]+1 << "\n"; // 문제의 특성상 거리+1이 정답
}→ vis배열 대신 거리를 저장하는 dist배열, 초기값은 -1로 하여 vis배열의 역할과 거리를 저장하는 역할을 동시에
0x03 응용2 - 시작점이 여러 개일 때
BOJ 7576번 : 토마토
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1002][1002];
int dist[1002][1002];
int m, n;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0 , -1};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
queue<pair<int , int> > Q;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin >> board[i][j];
if(board[i][j] == 1) Q.push(make_pair(i, j));
if(board[i][j] == 0) dist[i][j] = -1;
}
}
while(!Q.empty()) {
pair<int,int> cur = Q.front(); Q.pop();
for(int i=0; i<4; i++) {
int nx= cur.X + dx[i];
int ny= cur.Y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(dist[nx][ny] >= 0) continue;
dist[nx][ny] = dist[cur.X][cur.Y]+1;
Q.push(make_pair(nx, ny));
}
}
int mx=0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(dist[i][j]= -1) {
cout << -1;
return 0;
}
mx= max(mx, dist[i][j]);
}
}
cout << mx;
}→ 모든 시작점을 큐에 넣고 앞에서 한 것과 똑같이 BFS를 돌면 된다.
→ 쌓이는 순서는 반드시 거리 순이게 된다.
0x04 응용3 - 시작점이 두 종류일 때
BOJ 4179번 : 불!
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[1002];
int dist_F[1002][1002]; // 불의 전파 시간
int dist_J[1002][1002]; // 지훈이의 이동 시간
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=0; i<n; i++) {
fill(dist_F[i], dist_F[i]+m, -1);
fill(dist_J[i], dist_J[i]+m, -1);
}
for(int i=0; i<n; i++) cin >> board[i];
queue<pair<int, int> > Q_F;
queue<pair<int, int> > Q_J;
// 시작점 찾기
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(board[i][j]= 'F') {
Q_F.push(make_pair(i, j));
dist_F[i][j]= 0;
}
if(board[i][j]= 'J') {
Q_J.push(make_pair(i, j));
dist_J[i][j]= 0;
}
}
}
// 불의 BFS
while(!Q_F.empty()) {
pair<int, int> cur = Q_F.front(); Q_F.pop();
for(int i=0; i<4; i++) {
int nx= cur.X + dx[i];
int ny= cur.Y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(dist_F[nx][ny] >= 0 || board[nx][ny] == '#') continue;
dist_F[nx][ny] = dist_F[cur.X][cur.Y]+1;
Q_F.push(make_pair(nx, ny));
}
}
// 지훈이의 BFS
while(!Q_J.empty()) {
pair<int, int> cur = Q_J.front(); Q_J.pop();
for(int i=0; i<4; i++) {
int nx= cur.X + dx[i];
int ny= cur.Y + dy[i];
// 범위를 벗어났다는 것은 탈출에 성공했다는 것을 의미. 큐에 거리순으로 들어가므로 최초에 탈출한 시간을 출력
if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
cout << dist_J[cur.X][cur.Y]+1 << "\n";
return 0;
}
if(dist_J[nx][ny] >= 0 || board[nx][ny] == '#') continue;
// 불의 전파 시간을 조건에 추가
if(dist_F[nx][ny] != -1 && dist_F[nx][ny] <= dist_J[cur.X][cur.Y]+1) continue;
dist_J[nx][ny]= dist_J[cur.X][cur.Y]+1;
Q_J.push(make_pair(nx, ny));
}
}
// 여기에 도달한 것은 탈출에 실패한 것을 의미
cout << "IMPOSSIBLE\n";
}→ 시작점이 여러개이고 종류가 다르면 두 종류의 상호관계를 생각하면서 따로 BFS를 돌려서 해결할 수 있다.
하지만 여기서 불과 지훈이는 서로 영향을 주고받는 것이 아니라 불은 지훈이의 영향을 받지 않고 전파되어 나간다. 따라서 서로 영향을 주고받는 경우에는 백트래킹 기법이 필요하고, 시간 순으로 A와 B를 동시에 진행시켜야 한다.
0x05 응용4 - 1차원에서의 BFS
BOJ 1697번 : 숨바꼭질
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dist[100002];
int n, k;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
queue<int> Q;
fill(dist, dist+100002, -1);
cin >> n >> k;
dist[n] = 0;
Q.push(n);
while(!Q.empty()) {
int cur = Q.front(); Q.pop();
// range based for
for(int nxt : {cur-1, cur+1, 2*cur}) {
if(nxt < 0 || nxt > 100002) continue;
if(dist[nxt] != -1) continue;
dist[nxt] = dist[cur]+1;
Q.push(nxt);
}
}
cout << dist[k] << "\n";
}→ 등장인물이 0에서 100,000사이에 위치한다고해서 0에서 100,000사이만 이동한다는건 아님!!
이 문제에서는 운좋게 논리적으로 생각했을때 0에서 100,000사이에서만 움직이게 되었지만 다른 문제에서는 멋대로 가정한 것 때문에 문제를 말아먹을 수도 있다
문제 풀이
이번 강의에 해당하는 문제는 총 30개였다.
연습문제는 강의를 들으면서 잠시 멈춰놓고 해결하였고, 나머지 체크표시있는 중요한 문제들 먼저 BFS를 다시 복습하며 풀어보려고 한다.
Note_
7569번 토마토 : 연습문제의 토마토에서 3차원으로 해결해야한다는 점만 달랐다. 풀다가 pair가 아닌 tuple을 사용하는 방법을 배울 수 있었다.
tuple<int, int, int>로 선언하고, tie(curX, curY, curZ) = cur; 이렇게 사용하는 것을 배웠다.
2206번 벽 부수고 이동하기 : 하나의 벽을 부수고 이동할 수 있는 미로찾기 문제였다. 하지만 나는 어디에 벽을 부숴야할지 몰라서 모든 벽을 한번씩 부수고 이동한 거리를 저장했다가 최솟값을 출력하려고 하였으나 시간초과가 뜨고 꼬여버렸다. 답지를 보니 큐를 tuple로 변수 3개로 만들고 이동하다가 벽을 만났을때 부수고 온상태가 아니라면 그 벽을 부수고 이동하면 쉽게 해결되었다.
9466번 텀 프로젝트 : 문제를 읽으면서도, 읽고 고민하면서도 이게 왜 BFS문제인지 이해가 가질 않았고 시간 내 해결할 수 있는 해법도 떠오르지 않았다. 결국 바킹독님의 코드와 알고리즘 강의를 보면서 이해하였다. 보면서도 이해하는데 꽤 오랜시간이 걸렸고 쉽지 않았다.
1600번 말이 되고픈 원숭이 : boj 2206번 벽 부수고 이동하기와 같은 유형이라고 판단되어서 튜플로 3가지 변수로 큐를 생성하여서 많이 고민하였지만 아직 부족한것 같다 ,, 답지를 보니 거리를 저장하는 배열도 3차원으로 하여서 각각 나이트의 이동을 한 횟수만큼의 거리를 저장하였고, 마지막에 최솟값을 출력할 때 0x7f7f7f7f로 int최대값에 가깝게 설정을 한뒤 min함수로 반복문을 돌리고 값이 변하였으면 그 값을 출력하고 아니면 -1을 출력하도록 되어 있었다.
2146번 다리 만들기 : 가장 어려웠던 응용문제였다. 다리 길이의 최솟값을 구하기 전에 섬마다 번호를 부여하는 것 까지는 생각하고 구현하였으나, 그 뒤 다리 길이의 최솟값을 구하는 방식에 있어서 코드로 구현하는 구현성이 부족했다. 하지만 생각하는 것에 있어서는 BFS에 대해 깊이 생각할 수 있었고 발전한 것 같다. 방식은 모든 육지에서 BFS를 실행하되 다른 섬을 도착하게되면 그 거리를 최솟값 비교하여 저장해두는 방식으로 여러번의 BFS를 하는 것이였다.
리뷰
바킹독님이 강조하고 겁주신만큼 어렵고 많이 고민할 수 있는 단원이였다.
문제도 연습문제, 기본문제(체크)는 조금만 생각하면 풀 수 있는, 응용이 거의 없는 문제였다면 응용문제(체크)는 상당히 생각을 많이하게 되고 방법이 떠올라도 쉽게 구현되지 않는 어려움에 많이 처했다.
갈 길이 멀기에 나머지 문제들은 완강을 한 후에 다시 풀어보도록 하겠다.
다음은 0X0A DFS로 돌아오겠다.
출처: 바킹독님의 실전알고리즘 강의