문제를 보고 떠올린 해결책은 큐와 유니온파인드를 이용한 방식이다.
일단 처음에 물을 큐에 담고 큐에서 하나씩 꺼내 보면서 상하좌우 네 방향에서 만약 물이면 유니온파인드로 합쳐주고,
얼음이면 물로 바꾸고 큐에 날짜 정보를 포함시켜 담아준다.
백조 두개의 유니온파인드 그룹이 같을 때까지 반복하면 되고, 모든 점은 한번씩만 큐에 저장되도록 하면
최대 1500*1500만큼만 반복하면 되서 시간 안에 해결할 수 있다.
근데 그렇게 코드를 짜고 예제까지 통과했는데 메모리 초과로 풀 수 없었다.
맵에 대한 정보 1500*1500짜리 배열 말고도 유니온 파인드를 위한 1500*1500 배열이 하나 더 필요한데
설마 1500*1500 배열 2개로 터질줄은 몰랐다.
어떻게 해야 할지 모르겠어서 그냥 찾아봤는데 놀랍게도 그냥 백조를 계속 bfs해주는 간단한 방식으로 풀린다.
백조의 위치에서부터 갈 수 있는곳을 bfs해주고 물들도 bfs해주면서 얼음을 녹이고, 얼음이 녹았으면 또 bfs해주면서
백조 둘이 만날 때까지 반복하면 된다.
이렇게 하면 시간이 안될거라고 생각했는데 된다.
/*
#include<stdio.h>
#include<stack>
#include<queue>
using namespace std;
int R,C;
int parent[1504][1504];
int maps[1504][1504];
int firstx,firsty,secondx,secondy;
int ans;
struct Data{
int day,x,y;
bool operator<(const Data R)const{
return day>R.day;
}
};
priority_queue<Data>swan;
int finds(int ax,int ay)
{
if(ax*C+ay==parent[ax][ay]) return ax*C+ay;
else{
return parent[ax][ay]=finds(parent[ax][ay]/C,parent[ax][ay]%C);
}
}
void unions(int ax,int ay,int bx,int by)
{
if(finds(ax,ay)!=finds(bx,by))
{
parent[finds(ax,ay)/C][finds(ax,ay)%C]=finds(bx,by);
}
return;
}
int main()
{
scanf("%d %d",&R,&C);
firstx=-1;
for(int i=0;i<R;i++)
{
char x[1504];
scanf("%s",x);
for(int j=0;j<C;j++)
{
if(x[j]=='.')
{
maps[i][j]=0;
swan.push({0,i,j});
}
else if(x[j]=='X')
{
maps[i][j]=1;
}
else if(x[j]=='L')
{
if(firstx==-1){
firstx=i;
firsty=j;
}
else{
secondx=i;
secondy=j;
}
maps[i][j]=0;
swan.push({0,i,j});
}
}
}
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
{
parent[i][j]=i*C+j;
}
}
while(finds(firstx,firsty)!=finds(secondx,secondy))
{
Data t = swan.top();
swan.pop();
maps[t.x][t.y]=0;
int wx[4]={0,0,1,-1};
int wy[4]={1,-1,0,0};
for(int i=0;i<4;i++)
{
if(t.x+wx[i]>=R || t.x+wx[i]<0 || t.y+wy[i]>=C || t.y+wy[i]<0) continue;
if(maps[t.x+wx[i]][t.y+wy[i]]==0) unions(t.x,t.y,t.x+wx[i],t.y+wy[i]);
if(maps[t.x+wx[i]][t.y+wy[i]]==1){
swan.push({t.day+1,t.x+wx[i],t.y+wy[i]});
}
}
if(finds(firstx,firsty)==finds(secondx,secondy))
{
ans=t.day;
}
}
printf("%d",ans);
}
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include<stdio.h>
using namespace std;
int R, C;
vector<string> arr;
bool isFind = false;
pair<int, int> swan;
queue<pair<int, int>> sq, wq, tmpSQ, tmpWQ;
int dy[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
bool ch[1501][1501];
void swanBFS() {
while (!sq.empty()) {
int x = sq.front().first;
int y = sq.front().second;
sq.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dy[k][0];
int ny = y + dy[k][1];
if (nx < 0 || ny < 0 || nx >= R || ny >= C || ch[nx][ny]) continue;
ch[nx][ny] = true;
if (arr[nx][ny] == 'X') tmpSQ.push({ nx,ny });
else if (arr[nx][ny] == '.') sq.push({ nx,ny });
else if (arr[nx][ny] == 'L') {
isFind = true;
break;
}
}
}
}
void waterBFS() {
while (!wq.empty()) {
int x = wq.front().first;
int y = wq.front().second;
wq.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dy[k][0];
int ny = y + dy[k][1];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
if (arr[nx][ny] == 'X') {
arr[nx][ny] = '.';
tmpWQ.push({ nx,ny });
}
}
}
}
int meetDay() {
int day = 0;
while (!isFind) {
swanBFS();
if (isFind) break;
waterBFS();
sq = tmpSQ;
wq = tmpWQ;
while (!tmpSQ.empty()) tmpSQ.pop();
while (!tmpWQ.empty()) tmpWQ.pop();
day++;
}
return day;
}
int main() {
scanf("%d %d",&R,&C);
for (int i = 0; i < R; i++) {
string str;
cin >> str;
arr.push_back(str);
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < arr[i].size(); j++) {
if (arr[i][j] == 'L') {
swan.first = i;
swan.second = j;
}
if (arr[i][j] != 'X') {
wq.push({ i,j });
}
}
}
ch[swan.first][swan.second] = true;
sq.push(swan);
printf("%d",meetDay());
}주석처리된 부분은 처음에 생각한 풀이이다.
이론상 시간이 더 빠른데 메모리 때문에 실패한 풀이라서 아까워서 넣었다.
