인프런 커뮤니티 질문&답변

안녕하세요 선생님!

2가지 질문드릴게 있습니다!

1. 제가 만든 로직이 왜 시간초과인지 잘 모르겠고

2. 시간초과를 어떤식으로 해결해야할지 잘 모르겠습니다...

http://boj.kr/e32a513c49c94b99b253e5daedafde8c

#include <iostream>
#include <queue>
using namespace std;

const int dy[4] = { -1,1,0,0 };
const int dx[4] = { 0,0,-1,1 };

int R, C, sy, sx, ey, ex, ret;
int visited[1501][1501];
char adj[1501][1501];
queue<pair<int, int>> q;
queue<pair<int, int>> temp;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> R >> C;

	sy = -1;

	for (int y = 0; y < R; y++)
		for (int x = 0; x < C; x++)
		{
			cin >> adj[y][x];
			if (adj[y][x] == 'L')
			{
				if (sy == -1)
				{
					sy = y;
					sx = x;
				}
				else
				{
					ey = y;
					ex = x;
				}
			}
		}

	q.push({ sy,sx });
	visited[sy][sx] = 1;

	while (true)
	{
		// 백조끼리 만나나 못만나나 확인
		while (q.size())
		{
			int y = q.front().first;
			int x = q.front().second;
			q.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 (ny == ey && nx == ex)
				{
					cout << ret;
					return 0;
				}
				if (visited[ny][nx])
					continue;
				if (adj[ny][nx] == 'X')
					continue;

				visited[ny][nx] = visited[y][x];
				q.push({ ny,nx });
			}
		}

		// 빙판 녹이기
		for (int y = 0; y < R; y++)
			for (int x = 0; x < C; x++)
				if (adj[y][x] == 'X')
				{
					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 (adj[ny][nx] == '.' || adj[ny][nx] == 'L')
						{
							if (visited[ny][nx] != 0)
							{
								q.push({ y,x });
								visited[y][x] = visited[ny][nx];
							}
							temp.push({ y,x });
							break;
						}
					}
				}

		while (temp.size())
		{
			adj[temp.front().first][temp.front().second] = '.';
			temp.pop();
		}

		ret++;
	}

	return 0;
}