백준 3197 백조의 호수

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

3197번: 백조의 호수

 

1. 시간 복잡도 

시간복잡도를 알면 문제 접근법이 그나마 보인다. 주어지는 R과 C가 각각 1500 이하 이므로 약 10^3이다. 

O(N^2) 까지는 너끈하지만 O(N^3)은 10^9가 된다. 대강 10억이다... 이건 시간 제한 1초에 무조건 걸리므로

 

최대 O(N^2 * logN)인 알고리즘을 찾는다. (적어도 N^3은 안된다...)

 

2. 문제풀이

L이 백조이고 이 둘이 만나는 데 걸리는 날을 출력해야 한다.

 

빙판은 하루에 한번씩, 물 근처에 있는게 녹는다.

 

두 개의 Queue를 활용해서 BFS를 돌리려고 한다 

 

'며칠이나 걸리는가' 류의 문제는 BFS를 쓰는 게 좋은 것 같다. 방사형으로 체크할 수 있어서 그런 것 같다.

 

 

/* 백조의 호수 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define pp pair<int,int>
#define MAX 1500+1

using namespace std;

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

queue<pp> waterQ;
vector<pp> swanV;
char map[MAX][MAX];
bool is_visit[MAX][MAX];

void input();
bool is_range(int, int);
void solve();

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

	input();
	solve();

	return 0;
}

void input() {
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'L') {
				swanV.push_back({ i,j });
			}
			if (map[i][j] == 'L' || (map[i][j] == '.')) {
				waterQ.push({ i,j });
			}
		}
	}
}

bool is_range(int dr, int dc) {
	return dr >= 1 && dr <= R && dc >= 1&&  dc <= C;
}

void solve() {
	queue<pp> q;
	q.push(swanV[0]);	// 
	is_visit[swanV[0].first][swanV[0].second] = true; // 방문 체크


	int day = 0;
	while (true) {

		bool chk = false;
		queue<pp> nextQ;

		while (!q.empty()) { // 현재 백조가 이동할 수 있는 공간을 체크한다.
			int rr = q.front().first;
			int cc = q.front().second;
			q.pop();

			if (rr == swanV[1].first && cc == swanV[1].second) {
				chk = true;
				break;
			}

			for (int d = 0; d < 4; d++) {
				int nr = rr + dr[d]; // 사방을 확인한다. 
				int nc = cc + dc[d];

				if (is_range(nr, nc) == true && is_visit[nr][nc] == false) {
					is_visit[nr][nc] = true;

					if (map[nr][nc] == 'X')  // 백조의 인접 빙판은 내일 녹는다.
						nextQ.push({ nr,nc });

					else					// 지금 물인 곳을 백조가 헤엄쳐다닌다. 
						q.push({ nr, nc });
				}
			}
		}

		if (chk)
			break;

		q = nextQ;

		int water_size = waterQ.size(); // 한 번에 끝까지 돌리는 게 아니라 지금 큐에 있는것만 점검한다.
		while (water_size--) {
			int rr = waterQ.front().first;
			int cc = waterQ.front().second;
			waterQ.pop();

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

				if (is_range(nr, nc) == true && map[nr][nc] == 'X') {
					map[nr][nc] = '.';
					waterQ.push({ nr,nc });
				}
			}
		}
		day++;	// 하루 증가
	}

	cout << day << '\n';
}