알고리즘 설명
항상 방문먼저 한 뒤 큐에 넣자.
전형적인 기본 BFS
BOJ_1926번: 그림
문제
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.
입력
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)
출력
첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.
예제 입력 1
6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1
예제 출력 1
4
9
풀이
#include <bits/stdc++.h>
using namespace std;
array<array<int, 502>, 502> board;
array<array<bool, 502>, 502> vis;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n; // 세로 크기 (1 <= n <= 500)
int m; // 가로 크기 (1 <= m <= 500)
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++) cin >> board[i][j];
}
int mxarea = 0; // 그림의 최대값, 초기값이 음수면 안됨.
int cnt = 0; // 그림의 개수, 초기값이 음수면 안됨.
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == 0 || vis[i][j]) continue;
queue<pair<int,int>> Q;
vis[i][j] = true;
Q.push({i,j});
int area = 0;
cnt++;
while(!Q.empty()){
auto pos = Q.front();Q.pop();
int r = pos.first;
int c = pos.second;
area++;
for(int d = 0; d < 4; d++){
int nr = r + dr[d];
int nc = c + dc[d];
if(nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
if(board[nr][nc] == 0 || vis[nr][nc]) continue;
vis[nr][nc] = true;
Q.push({nr,nc});
}
}
mxarea = max(mxarea, area);
}
}
cout << cnt << "\n" << mxarea;
return 0;
}팁
아무것도 실행되지 않을 때를 생각해서 초기값 설정을 하자.
그림의 너비가 0이 되도록 하는 테스트 케이스와
그림의 개수가 0이 되도록 하는 테스트 케이스가 있을 수 있으니
초기값 설정을 음수로 설정하면 안된다.
응용1 - 거리측정
거리를 측정할 때는 vis배열 대신에 dist배열을 사용한다.
대신에 방문하지 않은 곳들을 모두 -1로 초기화 한다.
방문한 곳임을 조건확인할 때는 dist[r][c]>= 0 로 처리하자.
첫 칸을 거리에 포함할 때는 나중에 1 을 더해준다.
BOJ_2178번 : 미로 탐색
문제
N×M크기의 배열로 표현되는 미로가 있다.
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제 입력 1
4 6
101111
101010
101011
111011
예제 출력 1
15
팁
붙어있는 숫자를 입력받을 때는 string 자료형으로 입력받고 string을 마치 배열처럼 다루면 된다.
단, 비교할 때 숫자 타입이 아니라 문자 타입으로 비교해야 한다.
풀이
#include <bits/stdc++.h>
using namespace std;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N, M; // 행, 열
cin >> N >> M;
array<string, 102> miro;
for(int i = 0; i < N; i++) cin >> miro[i];
array<array<int, 102>, 102> dist;
for(int i = 0; i < N; i++){
fill(dist[i].begin(), dist[i].begin() + M, -1);
}
queue<pair<int,int>> Q;
dist[0][0] = 0;
Q.push({0,0});
while(!Q.empty()){
auto pos = Q.front();Q.pop();
int r = pos.first;
int c = pos.second;
for(int dir = 0; dir < 4; dir++){
int nr = r + dr[dir];
int nc = c + dc[dir];
if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
if(miro[nr][nc] == '0' || dist[nr][nc] >= 0) continue;
dist[nr][nc] = dist[r][c] + 1;
Q.push({nr,nc});
}
}
cout << dist[N-1][M-1] + 1;
return 0;
}응용2 - 시작점이 여러 개일 때
시작점이 여러 곳일 때는 시작 점을 미리 큐에 넣고 BFS를 실행하면 된다.
BOJ_7576: 토마토
문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
예제 입력 1
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
예제 출력 1
8
풀이
#include <bits/stdc++.h>
using namespace std;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N, M; // 행, 열
cin >> M >> N;
array<array<int, 1004>, 1004> board; // 1: 익은 토마토, 0: 안익은 토마토, -1: 빈공간
array<array<int , 1004>, 1005> dist; // -1: 방문안한 공간, 0이상 : 방문
// 입력 배열 초기화
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> board[i][j];
}
}
// 거리배열 초기화
for(int i = 0; i < N; i++) fill(dist[i].begin(), dist[i].begin() + M, -1);
// 시작점 찾아서 큐에 넣기
queue<pair<int,int>> Q;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(board[i][j] == 1){
dist[i][j] = 0;
Q.push({i,j});
}
}
}
// BFS
while(!Q.empty()){
auto cur = Q.front();Q.pop();
int r = cur.first;
int c = cur.second;
for(int dir = 0; dir < 4; dir++){
int nr = r + dr[dir];
int nc = c + dc[dir];
if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
if(board[nr][nc] == -1 || dist[nr][nc] >= 0) continue;
dist[nr][nc] = dist[r][c] + 1;
Q.push({nr,nc});
}
}
// 안익은 토마토 이면서 방문안한 곳 찾기, 있다면 early return
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(board[i][j] == 0 && dist[i][j] == -1){
cout << -1;
return 0;
}
}
}
// 모든 토마토가 다 익은 경우만 남음
// 거리배열에서 제일 큰 수를 찾으면 됨.
// 앞에서 배운대로 큰 수의 초기값을 뭘로 넣어야 될 지 고민해보자.
// 아무것도 안 한 경우 즉, 토마토가 원래부터 익어있는 경우에 0이 나와야 함.
int mx = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(dist[i][j] > mx) mx = dist[i][j];
}
}
cout << mx;
return 0;
}팁
반복문 한 번에 모든걸 해결하려고 하지말자.
어차피 시간복잡도에는 영향이 없다.
각 목적별로 반복문을 나누는 것이 디버깅에 유리하다.
응용3 - 시작점이 두 종류일 때
상황을 이해해야 한다.
A라는 BFS와 B라는 BFS가 있다고 가정하자.
A는 독립적인 전파가 가능하다.
B는 A의 전파에 영향을 받는다.
이 경우, 독립적인 A부터 전파하고 B는 그 결과에 따라 전파하면 된다.
BOJ_4179번: 불
문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
#: 벽
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
예제 입력 1
4 4
####
#JF#
#..#
#..#예제 출력 1
3
풀이
#include <bits/stdc++.h>
using namespace std;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
array<array<char, 1004>, 1004> jihun_board;
array<array<int, 1004>, 1004> jihun_dist;
array<array<char, 1004>, 1004> fire_board;
array<array<int, 1004>, 1004> fire_dist;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int R, C; // 행, 열
cin >> R >> C;
// 입력 배열 초기화
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++) {
cin >> jihun_board[i][j];
}
}
// 거리 배열 초기화
for(int i = 0; i < R; i++) fill(jihun_dist[i].begin(), jihun_dist[i].begin() + C, -1);
// 지훈배열, 불배열 따로 관리하기 위해 복사
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
fire_board[i][j] = jihun_board[i][j];
fire_dist[i][j] = jihun_dist[i][j];
}
}
// 불 시작점을 큐에 넣기
queue<pair<int,int>> Q;
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
if(fire_board[i][j] == 'F'){
fire_dist[i][j] = 0;
Q.push({i,j});
}
}
}
// 불 BFS
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
int r = cur.first;
int c = cur.second;
for(int dir = 0; dir < 4; dir++){
int nr = r + dr[dir];
int nc = c + dc[dir];
if(nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
if(fire_board[nr][nc] == '#' || fire_dist[nr][nc] >= 0) continue;
fire_dist[nr][nc] = fire_dist[r][c] + 1;
Q.push({nr, nc});
}
}
// 지훈 시작점 찾아서 큐에 넣기
bool flag = false; // 지훈위치 찾으면 반복문 바로 빠져나가기위한 플래그
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
if(jihun_board[i][j] == 'J'){
jihun_dist[i][j] = 0;
Q.push({i,j});
flag = true;
break;
}
}
if(flag) break;
}
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
int r = cur.first;
int c = cur.second;
for(int dir = 0; dir < 4; dir++){
int nr = r + dr[dir];
int nc = c + dc[dir];
if(nr < 0 || nc < 0 || nr >= R || nc >= C){
cout << jihun_dist[r][c] + 1;
return 0;
}
if(jihun_board[nr][nc] == '#' || jihun_dist[nr][nc] >= 0) continue;
if(fire_dist[nr][nc] >= 0 && fire_dist[nr][nc] <= jihun_dist[r][c] + 1) continue;
jihun_dist[nr][nc] = jihun_dist[r][c] + 1;
Q.push({nr,nc});
}
}
cout << "IMPOSSIBLE";
return 0;
}팁
지훈이는 불의 전파에 영향을 받지만 불은 지훈이에게 영향을 받지 않고 전파한다.
만약 물과 불처럼 각각 서로에게 영향을 줄 땐 백트래킹을 추가로 적용해서 풀어야 한다.
그 경우 불과 지훈이처럼 따로 전파하는게 아니라 시간 순으로 동시에 진행시켜야 한다.
또한, array 컨테이너와 같은 객체는 전역에서 선언하자.
main함수 내에서 사용하니 메모리 부족 문제가 생길 수 있다.
응용4 - 1차원에서의 BFS
2차원은 상하좌우로 뻗어나가지만 1차원에서는 좌우로만 뻗어나간다.
BOJ_1697번: 숨바꼭질
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17
예제 출력 1
4
풀이
수빈이와 동생의 위치가 애초에 같을 경우를 포함하기 위해
nx가 아닌 x위치에서 검사해야 한다.
#include <bits/stdc++.h>
using namespace std;
array<int, 100004> dist;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N, K; // N: 수빈이 위치, K: 동생 위치
cin >> N >> K;
// 거리배열 초기화
fill(dist.begin(), dist.end(), -1);
// 시작점 큐에 넣기
queue<int> Q;
dist[N] = 0;
Q.push(N);
// BFS
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
int x = cur;
// 수빈이와 동생이 같은 위치에서 시작할 경우 바로 종료해야 함.
// nx위치에서 조건으로 검사하면 이러한 로직을 놓치게 됨.
if(x == K){
cout << dist[x];
return 0;
}
for(int nx : {x-1, x+1, 2*x}){
if(nx < 0 || nx > 100000) continue;
if(dist[nx] >= 0) continue;
dist[nx] = dist[x] + 1;
Q.push(nx);
}
}
return 0;
}응용5 - 2차원에서 3차원으로 확장전파
BOJ_2206번: 벽 부수고 이동하기
문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
예제 입력 1
6 4
0100
1110
1000
0000
0111
0000
예제 출력 1
15
풀이
#include <bits/stdc++.h>
using namespace std;
array<string, 1004> board;
array<array<array<int,1004>, 1004>, 2> dist; // [0][r][c]: 벽 부수지않은 거리배열, [1][r][c]: 벽 부순 거리배열
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N, M;
cin >> N >> M; // 행 열
// 보드 배열 초기화
for(int i = 0; i < N; i++) cin >> board[i];
// 거리 배열 초기화
for(int k = 0; k< 2; k++){
for(int i = 0; i < N; i++){
fill(dist[k][i].begin(), dist[k][i].begin() + M, -1);
}
}
dist[0][0][0] = 0;
queue<tuple<int,int,int>> Q;
Q.push({0,0,0});
// 원본 BFS
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
int broken, r, c;
tie(broken,r,c) = cur;
if(r == N-1 && c == M-1){
cout << dist[broken][r][c] + 1;
return 0;
}
for(int dir = 0; dir < 4; dir++){
int nr = r + dr[dir];
int nc = c + dc[dir];
if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
if(dist[broken][nr][nc] >= 0) continue;
// 벽 부숨
if(broken == 0 && board[nr][nc] == '1'){
dist[1][nr][nc] = dist[0][r][c] + 1;
Q.push({1, nr, nc});
continue;
}
if(broken == 1 && board[nr][nc] == '1') continue;
dist[broken][nr][nc] = dist[broken][r][c] + 1;
Q.push({broken, nr, nc});
}
}
cout << -1;
return 0;
}팁
처음에는 벽을 부술때마다 마치 해당 지점을 시작점으로 모아두었다가 여러 시작점을 가지는 문제처럼 생각했다.
기존 BFS를 먼저 돌고, 벽을 부순 거리배열을 BFS로 따로 돌고 마지막에 값을 비교하는 방식이었다.
하지만 이 경우 BFS가 아니게 되므로 최적해를 보장할 수 없다.
벽을 부술때마다 해당 지점을 시작점으로 하는 방식은 어느 지점에서의 거리 배열 값은 1, 다른곳에서의 거리 배열 값은 2... 이렇게 레벨이 이미 달라져버리므로 BFS알고리즘이 아니다.
트리에서의 BFS를 생각해보자. 같은 레벨을 먼저 순회하고 다음 레벨로 넘어가야 BFS인데, 위의 경우는 같은 레벨을 순회하는 것이 아닌, 리프노드를 순회하는 형식이다.
따라서 BFS를 만족하기위해서는 벽을 부순 경로와 부수지 않은 경로를 구분없이 하나의 BFS에서 같이 돌려서 레벨을 맞춰야 한다.
그러기 위해서는 현재 경로가 이미 부순상태인지 부수지 않은 상태인지 판단할 수 있어야 하므로 노드에 플래그를 추가한다.
여기서의 노드는 거리배열의 노드를 의미하므로 거리배열은 1차원이 더해진 3차원이 된다.
벽을 만났을 때 continue하기 전에, 아직 벽을 부수지 않은 상태라면 벽 부순 거리배열로 전파하고 BFS순회를 위해 큐에 넣으면 된다.
