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

답변 감사합니다 ㅎㅎ
매번 초기 시작점에서부터 BFS가 불필요하게 일어납니다 <- 이 부분이 잘 이해가 안가서 그러는데요. 저는 while 문의 melt_ice, check_swan을 돌기전에 먼저 bfs_swan을 이용해서 백조가 다른 백조를 만날 수 있는지 확인을 하고 while문을 들어가는 로직으로 코드를 작성했는데 처음에 이 확인 작업이 잘못 되었다는 뜻인가요??

안녕하세요 02님 ㅎㅎ

아 제가 착각을 했는데요. 저게 매번 일어나는 거 같았는데 매번 안 일어나네요.

다만 불필요한 부분은 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int arr[1504][1504], visited[1504][1504];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
queue<pair<int, int>>ice;
queue<pair<int, int>>position;
vector<pair<int, int>>swan;
string str;
int r, c, cnt, sw;

void melt_ice()
{
	int x, y, nx, ny, qsize, flag;
	qsize = ice.size();
	queue<pair<int, int>>q;
	for (int i = 0; i < qsize; i++)
	{
		tie(y, x) = ice.front();
		ice.pop();
		flag = 0;
		for (int i = 0; i < 4; i++)
		{
			ny = y + dy[i];
			nx = x + dx[i];
			if (ny >= r || ny < 0 || nx >= c || nx < 0) continue;
			if (arr[ny][nx] == 0)
			{
				flag = 1;
				q.push({y, x});
				visited[y][x] = 0;
				break ;
			}
		}
		if (flag == 0)
			ice.push({y, x});
	}
	while (q.size())
	{
		tie(y, x) = q.front();
		q.pop();
		arr[y][x] = 0;
	}
}

void bfs_swan(int y, int x)
{
	int ny, nx;
	queue<pair<int, int>> q;
	visited[y][x] = 1;
	q.push({y, x});
	while(q.size())
	{
		tie(y, x) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			ny = y + dy[i];
			nx = x + dx[i];
			if (ny >= r || ny < 0 || nx >= c || nx < 0 || visited[ny][nx]) continue;
			visited[ny][nx] = 1;
			if (arr[ny][nx] == -1)
			{
				position.push({ny, nx});
				continue;
			}
			q.push({ny, nx});
			if (visited[swan[1].first][swan[1].second])
			{
				sw = 1;
				return;
			}
		}
	}
}

void check_swan()
{
	int x, y, nx, ny, psize, idx;
	queue<pair<int, int>> q;
	psize = position.size();
	idx = 0;
	while (idx < psize)
	{
		tie(y, x) = position.front();
		position.pop();
		q.push({y, x});
		visited[y][x] = 1;
		while (q.size())
		{
			tie(y, x) = q.front();
			q.pop();
			for (int i = 0; i < 4; i++)
			{
				ny = y + dy[i];
				nx = x + dx[i];
				if (ny >= r || ny < 0 || nx >= c || nx < 0 || visited[ny][nx]) continue;
				visited[ny][nx] = 1;
				if (arr[ny][nx] == -1)
				{
					position.push({ny, nx});
					continue;
				}
				q.push({ny, nx});
				if (visited[swan[1].first][swan[1].second])
				{
					sw = 1;
					return;
				}
			}
		}
		idx++;
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> r >> c;
	for (int i = 0; i < r; i++)
	{
		cin >> str;
		for (int j = 0; j < str.length(); j++)
		{
			if (str[j] == '.')
			{
				arr[i][j] = 0;
			}
			else if (str[j] == 'X')
			{
				arr[i][j] = -1;
				ice.push({i, j});
			}
			else
			{
				arr[i][j] = 0;
				swan.push_back({i, j});
			}
		}
	}
	bfs_swan(swan[0].first, swan[0].second);
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cout << visited[i][j];
		}
		cout <<'\n';
	}
//	while (ice.size() && sw == 0)
//	{
//		melt_ice();
//		cnt++;
//		check_swan();
//	}
	cout << cnt;
}

이렇게 한번 해볼까요?

이렇게 하고 ex3을 입력하면

00000000000000000
00000000000000000
00000001100000000
00000011110000000
00000011110000000
00000011111000000
00000011111000000
00000001111000000

이런식으로 나옵니다.

이 때 만들어진 position을 기반으로 check_swan이 동작합니다.

이 함수는 똑같은 로직이죠.

void check_swan()
{
	int x, y, nx, ny, psize, idx;
	queue<pair<int, int>> q;
	psize = position.size();

즉, 똑같은게 2번 반복됩니다.

또한, ice를 넣고

			else if (str[j] == 'X')
			{
				arr[i][j] = -1;
				ice.push({i, j});
			}

이런식으로 네방향을 기반으로 바깥쪽의 얼음을 찾은 아이디어는 좋으나 비효율적입니다.

		for (int i = 0; i < 4; i++)
		{
			ny = y + dy[i];
			nx = x + dx[i];
			if (ny >= r || ny < 0 || nx >= c || nx < 0) continue;
			if (arr[ny][nx] == 0)
			{
				flag = 1;
				q.push({y, x});
				visited[y][x] = 0;
				break ;
			}

바깥부분부터 시작해 탐색을 이어가면 바깥 얼음이라는 것은 자명하니 이부분은 신경쓸필요가 없게 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

감사합니다!!