백준 3197 백조의호수
by 진혀크
문제
- 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.
입력
- 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
각 R줄 동안 C만큼의 문자열이 주어진다.
’.’은 물 공간, ‘X’는 빙판 공간, ‘L’은 백조가 있는 공간으로 나타낸다.
출력
- 첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
예제
예제 입력
8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...
예제 출력
2
접근
- 1일차 : 일반적인 BFS로 처음에 접근했다. -> 실패했다.
- 2일차 : 이분탐색을 활용하여 접근했다. -> 실패했다.(솔직히 이걸로 통과할 줄 알았는데…ㅠ)
- 각각의 얼음(X)에서 BFS를 실행하면 그 얼음이 며칠째에 녹는지 알 수 있다. 따라서 빙하들이 녹는 날짜를 표기한 후 이분탐색으로 시간을 줄여보려 하였으나 실패!
- 3일차 : 앞으로 탐색해야 할 곳과 앞으로 녹을 얼음의 정보를 미리 Queue에 저장하는 방법 -> 성공
내가 생각한 풀이
- 녹은 지점의 주변의 얼음만 변한다 -> 미리 녹을 얼음을 알 수 있다.
- 기존에 탐색했던 부분은 탐색할 필요 없이 새롭게 녹은 부분에 대해서만 탐색을 이어 나가면 된다. -> n일차에 만나지 못하면 n-1일차에도 만나지 못하는 것이므로.
미처 생각하지 못했던것
- 백조 두 마리의 위치를 찾을 때 flag 라는 bool 변수를 사용했는데 0일때와 1일때로 구분을 했어야 했다. 근데 이걸 깜빡해서 1시간인가 2시간동안 헤맸다…
- 디테일에 더 신경쓸 것!
- n일차에는 n-1일차에 탐색한 곳을 다시 탐색할 필요가 없다는 점.
- 멍청하게 얼음을 녹이고 처음 위치에서 부터 BFS를 실행했다. Map의 크기가 1500 * 1500인데 당연히 시간, 메모리 초과가 날 수 밖에 없었다…
코드
#include<iostream>
#include<queue>
using namespace std;
int R, C, d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}, r = 0;
char map[1501][1501];
bool check[1501][1501] = {0, }, result_flag = 0;
pair<int, int> swan1, swan2;
queue<pair<int, int>> Q, WQ;
bool check_bound(int y, int x)
{
return (y>=0 && y<R && x>=0 && x<C);
}
void input()
{
cin>>R>>C;
bool flag = 0;
for(int i = 0 ; i<R ; i++)
{
for(int j = 0 ; j<C ; j++)
{
cin>>map[i][j];
if(map[i][j] == 'L')
{
if(flag == 0)
{
swan1.first = i;
swan1.second = j;
flag = 1; //어처구니 없이 빼먹어서 고생했던 부분. 디테일에 신경쓰자.
}
else
{
swan2.first = i;
swan2.second = j;
}
WQ.push({i,j});
}
else if(map[i][j] == '.')
WQ.push({i,j});
}
}
}
void search()
{
queue<pair<int, int>> NQ;
check[swan1.first][swan1.second] = 1;
while(!Q.empty())
{
pair<int, int> t = Q.front();
Q.pop();
if(t.first == swan2.first && t.second == swan2.second) //두 번째 백조가 있는 곳에 도달하면 break
{
result_flag = 1;
break;
}
for(int i = 0 ; i<4 ; i++)
{
int nextY = t.first + d[i][0], nextX = t.second + d[i][1];
if(!check_bound(nextY, nextX) || check[nextY][nextX] == 1) continue;
check[nextY][nextX] = 1; //.이던 X이던 그 지점에 대한 정보를 Queue에 넣었기 때문에 visit check를 해준다.
if(map[nextY][nextX] == '.' || map[nextY][nextX] == 'L')
{
Q.push({nextY, nextX});
}
else if(map[nextY][nextX] == 'X') //X라면 물과 맞닿아 있기 때문에 다음에 탐색할 지점이다.
{
NQ.push({nextY, nextX});
}
}
}
Q = NQ;
}
void changeMap()
{
int q_size = WQ.size();
while(q_size--)
{
pair<int, int> t = WQ.front();
WQ.pop();
for(int i = 0 ; i<4 ; i++)
{
int nextY = t.first + d[i][0], nextX = t.second + d[i][1];
if(!check_bound(nextY, nextX)) continue;
if(map[nextY][nextX] == 'X')
{
map[nextY][nextX] = '.';
WQ.push({nextY, nextX}); //변화가 일어난 지점에서만 또다른 변화가 일어나기 때문에 그 지점을 미리 알아놓는다.
}
}
}
}
int main(void)
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
input();
Q.push(swan1);
while(1)
{
search();
if(result_flag == 1)
{
cout<<r;
break;
}
changeMap();
r++;
}
return 0;
}
Subscribe via RSS