백준 3197번 백조의 호수

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... ...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... ..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... .XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ ..XXXXX...XXX.... ....XX.....X..... ................. ....XXXXX.XXX.... .....XX....X..... ................. 처음 첫째 날 둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

각 R줄 동안 C만큼의 문자열이 주어진다.

'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

 

녹이고 이동의 2BFS가 엮인 문제로 기존의 size만큼 BFS를 돌리는 기법으로 녹이는 건 잘 해결을 했으나, 

시간초과가 발생하였다. 그 이유는 1500x1500의 배열을 매 반복마다 초기화 해주는 과정때문..

따라서 이를 방지하기 위해서 백조는 물로만 이동할 수 있고 현재 백조의 위치에서 이동할 수 있는 얼음은 물에 인접한 얼음이라는 이야기가 된다. 따라서 다음 턴에 반드시 녹게 될 것이고 그 위치부터 백조가 다시 탐색하게 되므로,

초기 백조위치에서 다른 백조위치로 이동하지 않고 현재 백조 위치에서 인접한 얼음을 다음 백조 위치로 삼는 방식을 택하면 visit를 초기화 할 필요도 없고 같은경로를 반복 탐색하는 횟수도 줄어들게 된다.

 

 

#include <iostream>
#include <queue>
#include<string.h>
using namespace std;

int R, C;
char arr[1500][1500];
bool visit[1500][1500];
int posy, posx, stay, stax;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

int main(void)
{
	cin >> R >> C;
	posy = -1;
	posx = -1;

	queue<pair<int, int>> que;
	queue<pair<int, int> > swan;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 'L' && posy == -1 && posx == -1)
			{
				arr[i][j] = '.';
				posy = i;
				posx = j;
			}

			if (arr[i][j] == 'L' && posy != -1 && posx != -1)
			{
				arr[i][j] = '.';
				stay = i;
				stax = j;
			}

			if (arr[i][j] == '.')
			{
				que.push({ i,j });
			}

		}
	}
	int t = 0;
	swan.push({ posy,posx });
	visit[posy][posx] = true;

	while (1)
	{
		
		/*
		cout << t << "째날" << endl;
		for (int i = 0; i < R; i++)
		{
			for (int j = 0; j < C; j++)
			{
				cout << arr[i][j] << " ";
			}
			cout << endl;
		}
		*/
		bool flag = false;
		queue<pair<int, int> > newxQ;

		while (!swan.empty())
		{
			int y = swan.front().first;
			int x = swan.front().second;
			swan.pop();

			if (y == stay && x == stax)
			{
				flag = true;
				break;
			}

			for (int i = 0; i < 4; i++)
			{
				int newy = y + dy[i];
				int newx = x + dx[i];
				if (newy >= 0 && newy < R && newx >= 0 && newx < C)
				{
					if (!visit[newy][newx] && (arr[newy][newx] == '.'))
					{
						visit[newy][newx] = true;
						swan.push({ newy,newx });
					}
					else if (!visit[newy][newx] && (arr[newy][newx] == 'X'))
					{
						visit[newy][newx] = true;
						newxQ.push({ newy,newx });
					}
				}
			}
		}

		if (flag)
		{
			cout << t << endl;
			break;
		}

		swan = newxQ;

		int size = que.size();
		while (size--)
		{
			int y = que.front().first;
			int x = que.front().second;
			que.pop();

			for (int i = 0; i < 4; i++)
			{
				int newy = y + dy[i];
				int newx = x + dx[i];
				if (newy >= 0 && newy < R && newx >= 0 && newx < C)
				{
					if (arr[newy][newx] == 'X')
					{
						arr[newy][newx] = '.';
						que.push({ newy,newx });
					}
				}
			}
		}

		t++;

	}
}