최소이동 횟수 문제가 아닌 며칠에 만날 수 있는가에 대해 묻고 있으므로, 백조가 첫날 움직일 수 있는 모든 경로를 BFS 탐색한다. 만날 경우, 그대로 끝. 만나지 않을 경우, 백조 혹은 물 근처에 있던 얼음의 위치를 다음 날 백조가 위치할 수 있는 곳으로 판단하고 날짜를 하루 증가시킨다.
만날 때 까지 이를 반복한다.
이 문제는 백조가 만날수 있는지 확인하는 BFS, 백조가 움직일 수 있는 위치를 늘리는 BFS 두개를 이용하여 풀 수 있다. 다만 시간초과에 신경을 써야하므로 방문을 확인하는 것이 필수다.
하나만 사용한다면 그렇게 어렵지 않지만 두개의 BFS를 해야하니 난이도가 조금 있다.
시간 복잡도 O(N^2)
#include <iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
char map[1501][1501];
int day;
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,1,-1 };
int r, c;
bool chk[1501][1501], flag;
pair<int, int> swan;
queue < pair<int, int>> sq, wq, tmpSq, tmpWq;
void SwanBFS() {
while (!sq.empty()) {
int y = sq.front().first;
int x = sq.front().second;
sq.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= r || nx < 0 || nx >= c || chk[ny][nx] == 1) continue;
chk[ny][nx] = 1;
if (map[ny][nx] == 'X') tmpSq.push({ ny,nx });
else if (map[ny][nx] == '.') {
sq.push({ ny,nx });
}
else if (map[ny][nx] == 'L') {
flag = 1;
break;
}
}
}
}
void WaterBFS() {
while (!wq.empty()) {
int y = wq.front().first;
int x = wq.front().second;
wq.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
if (map[ny][nx] == 'X') {
map[ny][nx] = '.';
tmpWq.push({ ny,nx });
}
}
}
}
void solve() {
while (!flag) {
SwanBFS();
if (flag) break;
WaterBFS();
sq = tmpSq;
wq = tmpWq;
while (tmpSq.size()) tmpSq.pop();
while (tmpWq.size()) tmpWq.pop();
day++;
}
cout << day << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> r >> c;
for (int i = 0; i < r; i++) {
string s;
cin >> s;
for (int j = 0; j < c; j++) {
map[i][j] = s[j];
if (map[i][j] == 'L') {
swan.first = i;
swan.second = j;
}
if (map[i][j] != 'X') {
wq.push({ i,j });
}
}
}
chk[swan.first][swan.second] = 1;
sq.push(swan);
solve();
}