BFS (Breadth First Search)
다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
그래프에서 모든 노드를 방문하기 위한 알고리즘
예시 - (0,0)과 상하좌우로 이어진 모든 파란색 칸 BFS로 확인
(0,0) 방문했다는 표시 남기고 해당 칸 큐에 삽입
초기 세팅 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌효의 상하좌우를 살펴보면서 큐에 넣어주는 작업 반복
큐의 front는 (0,0)이고 pop
(0,0)의 상하좌우 칸 확인 -> 파란색 칸이면서 아직 방문하지 않은 칸 큐 삽입
...큐가 빌때까지 반복
큐가 비었을 때 확인해보면 (0,0)과 연결된 파란색 칸 모두 방문 완료
시간복잡도 : 모든 칸이 큐에 1번씩 들어가므로 칸이 N개일 때 O(N)
좌표 넣을 때 c++에서 활용하기 좋은 STL - pair
#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
}
미리 대소 관계 설정되어있음 : 앞쪽의 값 먼저 비교 -> 뒤쪽의 값 비교
위의 예시 코드
#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});
}
}
}
BFS 구현 시 자주 실수하는 점
1. 시작점에 방문했다는 표시를 남기지 않느낟.
2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남겼다.
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.
시작점이 여러개인 BFS 도는 방법
모든 시작점을 큐에 넣고 똑같이 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;
}
큐에 쌓이는 순서는 반드시 거리순...!
시작점이 두 종류일 때
// http://boj.kr/aed4ec552d844acd8853111179d5775d
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[1002];
int dist1[1002][1002]; // 불의 전파 시간
int dist2[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 >> n >> m;
for(int i = 0; i < n; i++){
fill(dist1[i], dist1[i]+m, -1);
fill(dist2[i], dist2[i]+m, -1);
}
for(int i = 0; i < n; i++)
cin >> board[i];
queue<pair<int,int> > Q1;
queue<pair<int,int> > Q2;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == 'F'){
Q1.push({i,j});
dist1[i][j] = 0;
}
if(board[i][j] == 'J'){
Q2.push({i,j});
dist2[i][j] = 0;
}
}
}
// 불에 대한 BFS
while(!Q1.empty()){
auto cur = Q1.front(); Q1.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(dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;
dist1[nx][ny] = dist1[cur.X][cur.Y]+1;
Q1.push({nx,ny});
}
}
// 지훈이에 대한 BFS
while(!Q2.empty()){
auto cur = Q2.front(); Q2.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){ // 범위를 벗어났다는 것은 탈출에 성공했다는 의미. 큐에 거리 순으로 들어가므로 최초에 탈출한 시간을 출력하면 됨.
cout << dist2[cur.X][cur.Y]+1;
return 0;
}
if(dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y]+1) continue; // 불의 전파 시간을 조건에 추가
dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
Q2.push({nx,ny});
}
}
cout << "IMPOSSIBLE"; // 여기에 도달했다는 것은 탈출에 실패했음을 의미.
}
'algorithm > 정리' 카테고리의 다른 글
알고리즘 - 기초 코드 작성 요령 (0) | 2024.04.14 |
---|---|
재귀 (0) | 2024.04.11 |
자바 기본 자료구조 선언 정리 (0) | 2024.04.09 |
그리디 알고리즘 (0) | 2024.04.09 |
DP (다이나믹 프로그래밍) (0) | 2024.04.08 |