[C++] BOJ(백준) 3197 백조의 호수

https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

 

BFS 문제다.

 

이 문제를 푸는데 2~3일 정도 걸렸다.

문제는 백조 두 마리가 존재하고 이 백조들이 만나는 데까지 소요되는 날을 구하는 문제다.

이 사이에는 얼음이 존재하고, 이 얼음은 물과 접촉해 있을 때 녹는다.

 

처음 생각한 방법은 단순하게 얼음을 녹이고, 백조의 경로를 찾고를 반복하는 것이었다.

구현해볼 것도 없이 시간 초과가 날 것이기 때문에 바로 패스했다.

 

두 번째 생각한 방법은 먼저 백조를 만나게 하는 경로를 구하는 것이다.

이 때 조건은 얼음을 최대한 적게 지나는 경로다. 그리고 그 경로를 저장해 되돌아 가며 연속된 얼음 개수를 찾는 것이다.

연속된 얼음 개수 / 2를 해주면 소요되는 날이라고 생각했는데 아래와 같은 반례를 찾았다.

 

마지막이 해결한 방법이다.

먼저 얼음을 다 녹이고 해당 칸의 얼음이 녹는데 소요되는 날을 저장한다.(visit 배열)

이 때 계속 모든 배열을 탐색하는 것이 아닌, 현재 녹은 얼음을 큐에 저장하여 해당 큐로 다시 얼음을 녹인다.

그리고 백조가 만나는 경로를 탐색하여 경로에서 visit 배열의 값 중 가장 큰 값이 작아지도록 해야한다.

 

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

int n, m;
int sr = -1, sc = -1, fr = -1, fc = -1;

char arr[1500][1500];
int visit[1500][1500];
int vis[1500][1500];

int dr[4] = { 1, -1, 0, 0 };
int dc[4] = { 0, 0, 1, -1 };

queue<pair<int, int>> q;

void ice() {
	queue<pair<int, int>> temp;
	do {
		while (!temp.empty()) temp.pop();
		while (!q.empty()) {
			int r = q.front().first;
			int c = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];

				if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
				if (visit[nr][nc]) continue;
				if (arr[nr][nc] == 'X') {
					visit[nr][nc] = visit[r][c] + 1;
					temp.push({ nr, nc });
				}

			}
		}
		q = temp;
	} while (temp.size());
}

void bfs() {
	queue<pair<int, int>> qq;
	qq.push({ sr, sc });
	vis[sr][sc] = 0;

	while (!qq.empty()) {
		int r = qq.front().first;
		int c = qq.front().second;
		qq.pop();

		int tmp; 

		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];

			if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;

			tmp = max(visit[nr][nc], vis[r][c]);
			if (vis[nr][nc] != 750 && vis[nr][nc] <= tmp) continue;

			vis[nr][nc] = tmp;
			qq.push({ nr, nc });
		}
	}

	cout << vis[fr][fc];
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			vis[i][j] = 750;
			cin >> arr[i][j];
			if (arr[i][j] == 'L') {
				if (sr == -1) {
					sr = i;
					sc = j;
				}
				else {
					fr = i;
					fc = j;
				}
			}
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (arr[i][j] != 'X') {
				for (int k = 0; k < 4; k++) {
					int r = i + dr[k];
					int c = j + dc[k];

					if (r < 0 || c < 0 || r >= n || c >= m) continue;
					if (arr[r][c] == 'X') {
						q.push({ i, j });
						break;
					}

				}
			}
		}
	ice();

	bfs();

}