단순 반복 bfs
문제 같지만 R,C 범위가 크기 때문에 반복적으로 bfs
를 돌리다 보면 메모리 초과나 시간 초과가 발생할 수 있다.
우선 2단계로 풀이가 나누어지는데 1단계는 백조끼리 서로 만날 수 있는지 체크하고 그 다음 물과 인접해있는 얼음을 녹이는 과정이 필요하다.
백조끼리 서로 만나는지 확인하기 위해서는 bfs
를 이용하면 되지만 한쪽 백조에서 출발하게 되면 탐색했던 범위를 반복해서 탐색하기 때문에 비효율적이다. 그렇기 때문에 다른쪽 백조를 찾기위해서 bfs
탐색 도중 만나게 되는 얼음들을 저장해두었다가 다음 탐색에 사용한다.
다음 단계는 물과 인접해 있는 얼음들을 녹이는 과정인데 여기서도 모든 물의 좌표를 저장해두면 순회하는데 시간이 많이 걸리기 때문에 물과 인접해 있는 얼음(이번에 녹을 얼음)좌표를 저장해두었다가 사용하면 효율적으로 풀이할 수 있다.
#include <bits/stdc++.h>
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };
using namespace std;
int R, C;
string arr[1501];
bool visited[1501][1501];
vector<pair<int, int>> target;
queue<pair<int, int>> v;
int main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
cin >> R >> C;
for (int i = 0; i < R; i++) {
cin >> arr[i];
for (int j = 0; j < C; j++) {
if (arr[i][j] == 'L') {
target.push_back({ j, i });
arr[i][j] = '.';
v.push({ j, i });
}
else if (arr[i][j] == '.') v.push({ j, i });
}
}
queue<pair<int, int>> q;
int ans = 0;
q.push(target[0]);
visited[target[0].second][target[0].first] = true;
while (true) {
queue<pair<int, int>> next;
while (!q.empty()) {
int r = q.front().second;
int c = q.front().first;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = dx[i] + c;
int ny = dy[i] + r;
if (nx < 0 || ny < 0 || nx >= C || ny >= R || visited[ny][nx]) continue;
else if (target[1] == make_pair(nx, ny)) {
cout << ans;
return 0;
}
else if (arr[ny][nx] == 'X') next.push({ nx, ny });
else q.push({ nx ,ny });
visited[ny][nx] = true;
}
}
q = next;
ans++;
int n = v.size();
while(n--) {
int r = v.front().second;
int c = v.front().first;
v.pop();
for (int j = 0; j < 4; j++) {
int nx = dx[j] + c;
int ny = dy[j] + r;
if (nx < 0 || ny < 0 || nx >= C || ny >= R) continue;
else if (arr[ny][nx] == 'X') {
v.push({ nx, ny });
arr[ny][nx] = '.';
}
}
}
}
return 0;
}