[백준 3197] 백조의 호수

백조의 호수 3197

유형

• bfs

풀이

단순 반복 bfs문제 같지만 R,C 범위가 크기 때문에 반복적으로 bfs를 돌리다 보면 메모리 초과나 시간 초과가 발생할 수 있다.

우선 2단계로 풀이가 나누어지는데 1단계는 백조끼리 서로 만날 수 있는지 체크하고 그 다음 물과 인접해있는 얼음을 녹이는 과정이 필요하다.

백조끼리 서로 만나는지 확인하기 위해서는 bfs를 이용하면 되지만 한쪽 백조에서 출발하게 되면 탐색했던 범위를 반복해서 탐색하기 때문에 비효율적이다. 그렇기 때문에 다른쪽 백조를 찾기위해서 bfs탐색 도중 만나게 되는 얼음들을 저장해두었다가 다음 탐색에 사용한다.

다음 단계는 물과 인접해 있는 얼음들을 녹이는 과정인데 여기서도 모든 물의 좌표를 저장해두면 순회하는데 시간이 많이 걸리기 때문에 물과 인접해 있는 얼음(이번에 녹을 얼음)좌표를 저장해두었다가 사용하면 효율적으로 풀이할 수 있다.

코드

#include <bits/stdc++.h>

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

using namespace std;

int R, C;
string arr[1501];
bool visited[1501][1501];
vector<pair<int, int>> target;
queue<pair<int, int>> v;


int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		cin >> arr[i];
		for (int j = 0; j < C; j++) {
			if (arr[i][j] == 'L') {
				target.push_back({ j, i });
				arr[i][j] = '.';
				v.push({ j, i });
			}
			else if (arr[i][j] == '.') v.push({ j, i });
		}
	}

	queue<pair<int, int>> q;
	int ans = 0;
	q.push(target[0]);
	visited[target[0].second][target[0].first] = true;
	while (true) {
		queue<pair<int, int>> next;
		while (!q.empty()) {
			int r = q.front().second;
			int c = q.front().first;
			q.pop();

			for (int i = 0; i < 4; i++) {
				int nx = dx[i] + c;
				int ny = dy[i] + r;
				if (nx < 0 || ny < 0 || nx >= C || ny >= R || visited[ny][nx]) continue;
				else if (target[1] == make_pair(nx, ny)) {
					cout << ans;
					return 0;
				}
				else if (arr[ny][nx] == 'X') next.push({ nx, ny });
				else q.push({ nx ,ny });
				visited[ny][nx] = true;
			}
		}
		q = next;
		ans++;

		int n = v.size();
		while(n--) {
			int r = v.front().second;
			int c = v.front().first;
			v.pop();
			for (int j = 0; j < 4; j++) {
				int nx = dx[j] + c;
				int ny = dy[j] + r;
				if (nx < 0 || ny < 0 || nx >= C || ny >= R) continue;
				else if (arr[ny][nx] == 'X') {
					v.push({ nx, ny });
					arr[ny][nx] = '.';
				}
			}
		}
	}

	
	return 0;
}