알고리즘 소개
BFS(Breath First Search): 너비 우선 탐색
예시
1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번을 반복
처음 방문 했을 때만 방문 표시를 남기기 때문에 모든 칸이 큐에 1번씩 들어간다. 따라서 시간복잡도는 칸이 N개일 때 O(N)이다. 같은 원리로 행이 R개, 열이 C개인 2차원 평면을 BFS 탐색하면 시간복잡도는 O(RC)가 될 것이다.
이제 BFS 구현에 필요한 pair STL에 대해 알아보고자 한다. pair를 이용하면 두 자료형을 묶어서 가지고 다닐 수 있다. pair는 BFS 구현에서 큐에 좌표를 넣을 때 사용한다.
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 이상에서는 make_pair 대신 중괄호만을 사용해도 된다.
cout << t2.first << ' ' << t2.second << '\n'; // 4 6
if(t2< t1) cout << " t2 < t1"; //t2 < t1
}레퍼런스: http://www.cplusplus.com/reference/utility/pair/
https://cplusplus.com/reference/utility/pair/
second_typeThe second template parameter (T2)Type of member second.
cplusplus.com
BFS는 코딩테스트에서 정말 정말 빈출되는 주제이므로 효율적인 코드를 거의 외우다시피 하는 것이 좋다.
#include <bits/stdc++.h>
using namespace std;
#define X first //t.first, t.second 대신 t.X 이런식으로 간단하게 작성하고 싶어서 변수 선언
#define Y second
int board[502][502] = {...}; //탐색해야하는 칸. 1이면 방문 가능, 0이면 방문 불가능 경로
bool vis[502][502]; //방문 여부 표시 배열
int n = 7, m = 10; //행과 열의 개수
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}); //큐에 좌표를 추가
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]; //8, 9번째 줄 코드를 참고하면 (dx[dir],dy[dir])값이 (1,0),(0,1),(-1,0),(0,-1)임을 알 수 있다.
int ny = cur.Y + dy[dir]; //nx, ny값에 하, 우, 상, 좌 값이 순서대로 담기는 것을 알 수 있다.
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({nx, ny}); //큐에 추가
}
}
}
또한 대부분의 BFS에서 x가 행, y가 열임에 유의해야 한다.
BFS 구현 시 자주 하는 실수
1. 시작점에 방문했다는 표시를 남기지 않는다. 이렇게 되면 시작점을 두 번 방문하는 문제가 일어날 수 있다.
2. 큐에 넣을 때 해당 칸에 방문했다는 표시를 하는 대신, 큐에서 뺼 때 방문했다는 표시를 남긴다. 이렇게 되면 같은 칸이 큐에 여러 번 들어가 메모리 초과나 시간 초과가 날 수 있다. 특히 이런 실수의 경우 적은 수의 test case에 대해서는 문제 없이 돌아가다가 실제 제출했을 때 터지는 경우가 있어서 주의해야 한다.
3. nx, ny가 배열 밖으로 벗어났는지 확인하지 않는다.
응용 1 - 거리 측정
BOJ 1926번
hint) 이 문제를 해결하기 위해 고려해야 하는 일은 두가지이다.
1. 상하좌우로 연결된 그림의 크기를 알아내기 - 큐에서 pop()을 몇 번 진행하는지를 통해 알 수 있다.
2. 도화지에 있는 모든 그림을 찾아내기 - 이중 for문을 돌면서 새로운 그림인지 확인함을 통해 총 그림의 개수를 파악할 수 있다.
// http://boj.kr/2edfa3c97260480d81e3133d389c119f
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502]; // 1이 파란 칸, 0이 빨간 칸에 대응
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 mx = 0; // 그림의 최댓값
int num = 0; // 그림의 수
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){ // (i, j)를 시작점으로 하고 싶은 상황
if(board[i][j] == 0 || vis[i][j]) continue; // 해당 칸이 색칠이 안된 부분(0)이거나 이미 (i, j)를 방문했을 경우 넘어감
// (i,j)는 새로운 그림에 속해있는 시작점
num++; // 그림의 수 1 증가
queue<pair<int,int> > Q;
vis[i][j] = 1; // (i,j)로 BFS를 시작하기 위한 준비
Q.push({i,j});
int area = 0; // 그림의 넓이
while(!Q.empty()){
area++; // 큐에 들어있는 원소를 하나 뺄 때 마다 넓이를 1 증가시킴
pair<int,int> cur = Q.front(); Q.pop();
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});
}
}
// (i, j)를 시작점으로 하는 BFS가 종료됨
mx = max(mx, area); // area가 mx보다 클 경우 mx에 area를 대입. max는 STL에 정의된 함수
}
}
cout << num << '\n' << mx;
}응용 2 - 시작점이 여러 개일 때
BOJ 2178번: 미로 탐색
다차원 배열에서의 거리 측정 문제이다. 이 문제는 미로의 좌측 상단에서 시작해 우측 하단으로 가는 최단 경로를 찾는 문제이다. BFS를 이용하면 하나의 점에서 모든 점으로의 최단 경로를 알 수 있다.
(0,0)에서 시작하는 BFS를 떠올려보자. 원래 우리는 다음과 같이 까만 점을 이용해 BFS에서 이미 방문한 칸을 표시했다.
그런데 이 문제를 해결하기 위해서는 까만 점 대신 이렇게 숫자를 적어줘야 한다. 각 칸에 적힌 숫자는 그 칸으로부터 (0,0)까지의 거리이다. 빨간색 칸은 현재 보고 있는 칸이고, 검정색 칸은 새롭게 방문되는 칸이다. 현재 보고 있는 칸으로부터 추가되는 인접된 칸은 현재 칸의 숫자보다 1만큼 증가된 숫자 값을 가지게 된다. 현재 칸보다 한 번 더 이동해야 해당 칸에 도달할 수 있기 때문이다.
// http://boj.kr/cd14bec9ecff461ab840f853ed0eb87f
#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(void){
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({0,0});
dist[0][0] = 0;
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
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(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue;
dist[nx][ny] = dist[cur.X][cur.Y]+1;
Q.push({nx,ny});
}
}
cout << dist[n-1][m-1]+1; // 문제의 특성상 거리+1이 정답
}응용 3 - 시작점이 두 종류일 때
BOJ 7576번: 토마토
익은 토마토의 주변에 존재하는 안 익은 토마토가 익는 데는 하루가 걸린다. 따라서 시작점인 익은 토마토로부터 BFS를 돌면서 안 익은 토마토까지의 거리를 구하면 토마토들이 모두 익는 데 몇 일이 걸리는지 알 수 있다.
이 문제의 관건은 '익은 토마토가 여러 개일 때 시작점을 어떻게 설정해야 하는가?'이다. 각 익은 토마토들에 대해 BFS를 모두 돌리는 방법도 있지만, 그러면 BFS의 시간복잡도가 O(NM)이고, 익은 토마토의 최대 개수가 NM개이므로 총 시간복잡도가 최대 O(N^2M^2)가 되기 때문에 시간초과가 일어날 수 있다.
시작점이 여러 개인 BFS를 구현할 때는 모든 시작점을 큐에 넣고 BFS를 돌리면 된다. 다음 그림에서 초록 칸은 익은 토마토, 파란 칸은 익지 않은 토마토, 빨간 칸은 토마토가 없는 곳을 의미한다. 익은 토마토가 2개 있는 상황인 셈인데, 이 두 개를 큐에 넣고 BFS를 돌리면 그림에서처럼 거리가 잘 구해진다.
// http://boj.kr/ae38aa7eb7a44aca87e9d7928402d040
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1002][1002];
int dist[1002][1002];
int 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);
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({i,j});
if(board[i][j] == 0)
dist[i][j] = -1;
}
}
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
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(dist[nx][ny] >= 0) continue;
dist[nx][ny] = dist[cur.X][cur.Y]+1;
Q.push({nx,ny});
}
}
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(dist[i][j] == -1){
cout << -1;
return 0;
}
ans = max(ans, dist[i][j]);
}
}
cout << ans;
}응용 4 - 1차원에서의 BFS
BOJ 1697번: 숨바꼭질
이번 문제는 앞에서 다룬 2차원 배열에서의 BFS 문제들과 결이 다르다고 느껴질 수 있다. 미로 탐색이나 토마토 문제에서는 각 칸에서부터 상, 하, 좌, 우로 이동할 수 있었지만 이번엔 그렇지 않기 때문이다. 하지만 조금 고민해보면 이전 문제들의 상, 하, 좌, 우와 마찬가지로 수빈이가 위치 X에 있다고 가정할 때 X-1, X+1, 2*X 중 한 칸으로 이동 가능하다는 것을 알 수 있다. 다음 그림을 통해 예를 들어보자. 수빈이가 위치 5에 있다고 하면 1초 후에 4, 6, 10 중 한 칸으로 이동할 수 있다.
이후 큐에 가장 앞에 존재하는 4를 기준으로 X-1, X+1, 2*X값을 구하면 3, 5, 8인데, 5는 이미 방문했으므로 3과 8에 2를 대입한 한 후 큐에 넣으면 된다.
이런 과정을 반복하면서 BFS를 돌다가 동생의 위치에 도달하게 되면 문제에서 원하는 시간을 구할 수 있다.
이 문제에서 생각해볼 점은 'BFS의 범위를 어떻게 설정해야 하는가?'이다. 문제에서는 수빈이와 동생의 위치 차이가 0에서 100,000 사이라고 했지, 수빈이가 이동 중에 반드시 0에서 100,000 사이에 있어야한다는 말은 없음에 유의해야 한다.
// http://boj.kr/ba53d62b7651443cbf7b2028c28ce197
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dist[100002];
int n,k;
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
fill(dist, dist+100001,-1);
dist[n] = 0;
queue<int> Q;
Q.push(n);
while(dist[k] == -1){
int cur = Q.front(); Q.pop();
for(int nxt : {cur-1, cur+1, 2*cur}){
if(nxt < 0 || nxt > 100000) continue;
if(dist[nxt] != -1) continue;
dist[nxt] = dist[cur]+1;
Q.push(nxt);
}
}
cout << dist[k];
}'Computer Algorithms' 카테고리의 다른 글
| [바킹독 실전 알고리즘 0x0C] 백트래킹 (0) | 2023.02.10 |
|---|---|
| [바킹독 실전 알고리즘 0x0A] DFS (0) | 2023.02.05 |
| [바킹독 실전 알고리즘 0x08] 스택의 활용(수식의 괄호 쌍) (0) | 2023.02.02 |
| [바킹독 실전 알고리즘 0x07] 덱 (0) | 2023.02.01 |
| [C++] Visual Studio에 <bits/stdc++.h> 헤더파일 추가하기 (0) | 2023.02.01 |
댓글