https://www.acmicpc.net/problem/3197
3197번: 백조의 호수
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
www.acmicpc.net
bfs로 해결한 문제였습니다.
📕 풀이방법
📔 입력 및 초기화
호수의 세로, 가로 길이를 저장할 변수 r, c, 빙하를 제거하기 위해 물의 (행, 열) 좌표들을 저장하는 waterQ, 백조가 다닐 수 있는 최전선 범위의 좌표들이 담겨있는 swanQ, 백조 두 마리의 좌표가 저장된 vector 변수 swan, 호수의 모양을 저장할 이차원 문자 배열 lake, 답을 출력할 timer 상 하 좌 우 네 방향을 확인하기 위한 일차원 배열 dx, dy를 선언합니다.
1. r, c를 입력받습니다
2. r x c만큼 lake에 입력합니다. 이 때 백조는 물 위에 있기 때문에 'L'인 경우에도 waterQ에 push합니다. 그 외에 'L'인 경우 swan에 각 백조의 좌표를 저장합니다.
3. 마지막으로 0번째 백조부터 시작할 예정이므로 0번째 swan의 좌표를 swanQ에 push합니다.
📔 풀이과정
크기가 최대 1500 x 1500까지 가질 수 있으니 이는 대략 200만으로 매번 bfs를 수행할 시 시간초과가 나게 됩니다. 따라서 중복 탐색을 없애고 효율적으로 탐색하는 방법으로 해결할 수 있습니다.
1. 0번째 백조부터 출발해서 1번째 백조와 만날 수 있는지 여부를 확인합니다. 만날 수 없다면 다음 날에 빙하가 녹은 구역들의 좌표는 0번째 백조가 다닐 수 있습니다. 따라서 확인하는 도중 다음에 확인하기 위해 백조의 좌표를 넣어줍니다. 이때는 임시 queue s가 사용됩니다.
2. 다음 날 백조가 다닐수 있는 최전선의 좌표들이 저장되었습니다. 이제는 다음날이 되어 녹아 물이된 곳들의 좌표를 저장해야합니다. 저장된 waterQ의 size만큼 확인한다면 다음 날에 녹을 빙하들의 좌표들을 빠르게 확인할 수 있습니다. 현재 날의 시점에서 waterQ의 좌표들과 인접한 곳들 중 빙하 'X'가 있다면 그 구역을 물로 만들어주고 waterQ에 넣어줍니다.
3. 0번 백조가 계속해서 녹은 빙하쪽으로 이동하며 1번 백조와 빠르게 만나게 됩니다. 만났다면 그 날을 출력해줍니다.
📔 정답출력
timer를 출력합니다.
📕 Code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int r, c, ck[1501][1501], timer;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
char lake[1501][1501];
struct Swan {int r,c; };
vector <Swan> swan;
queue <pii> swanQ, waterQ;
void meltIce(){
int wSize = waterQ.size();
while(wSize--){
int x = waterQ.front().first;
int y = waterQ.front().second;
waterQ.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(0 > nx || nx >= r || 0 > ny || ny >=c) continue;
if(lake[nx][ny] != 'X') continue;
waterQ.push({nx,ny});
lake[nx][ny] = '.';
}
}
}
bool canMeet(){
queue <pii> s;
while(!swanQ.empty()){
int x = swanQ.front().first;
int y = swanQ.front().second;
swanQ.pop();
if(x == swan[1].r && y == swan[1].c) return true;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(0 > nx || nx >= r || 0 > ny || ny >= c) continue;
if(ck[nx][ny]) continue;
ck[nx][ny] = 1;
if(lake[nx][ny] == 'X') s.push({nx,ny}); //다음날에 다닐수 있다.
else swanQ.push({nx,ny});
}
}
swanQ = s;
return false;
}
int main(){
cin >> r >> c;
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++) {
cin >> lake[i][j];
if(lake[i][j] == 'L') waterQ.push({i,j}),swan.push_back({i,j});
if(lake[i][j] == '.') waterQ.push({i,j});
}
}
swanQ.push({swan[0].r,swan[0].c});
while(1){
if(canMeet()) break;
timer++;
meltIce();
}
cout << timer;
}
'Algorithm > BFS' 카테고리의 다른 글
(C++) - 백준(BOJ) 17129번 : 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 (0) | 2021.09.20 |
---|---|
(C++) - 백준(BOJ) 16932번 : 모양 만들기 (0) | 2021.09.18 |
(C++) - 백준(BOJ) 16954번 : 움직이는 미로 탈출 (0) | 2021.08.23 |
(C++) - 백준(BOJ) 2021번 : 최소 환승 경로 (4) | 2021.08.17 |
(C++) - 백준(BOJ) 5214번 : 환승 (0) | 2021.08.17 |