# 3197 백조의 호수

## 답지 참조 버전

```cpp
#include"3197.h"
using namespace std;
typedef pair<int, int> pii;
#define fastio cin.tie(0)->sync_with_stdio(0)

void B3197::Solution()
{
	fastio;

	int R, C;
	cin >> R >> C;
	vector<string> lake(R);
	for (int i = 0; i < R; i++)
		cin >> lake[i];
	
	queue<pii> waterq;
	pii duck;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (lake[i][j] == '.') {
				waterq.push({ i,j });
			}
			else if (lake[i][j] == 'L') {
				waterq.push({ i,j });
				duck = { i,j };
			}
		}
	}

	vector<int> dx = { 1,-1,0,0 };
	vector<int> dy = { 0,0,1,-1 };

	vector<vector<bool>> visited(R, vector<bool>(C,false));
	queue<pii> duckq;
	queue<pii> nextdq;
	visited[duck.first][duck.second] = true;
	nextdq.push(duck);
	bool found = false;
	int day = 0;
	while (1)
	{
		duckq = nextdq;
		nextdq = queue<pii>();
		while (!duckq.empty())
		{
			pii d = duckq.front(); duckq.pop();
			for (int i = 0; i < 4; i++) {
				int newx = d.first + dx[i], newy = d.second + dy[i];
				if (0 <= newx && newx < R && 0 <= newy && newy < C
					&& !visited[newx][newy]) {
					if (lake[newx][newy] == '.') { duckq.push({ newx,newy }); }
					else if (lake[newx][newy] == 'X') { nextdq.push({ newx,newy }); }
					else if (lake[newx][newy] == 'L') { found = true; break; }
					visited[newx][newy] = true;
				}
			}
		}
		if (found) break;

		int qlen = waterq.size();
		while (qlen--)
		{
			pii w = waterq.front(); waterq.pop();
			for (int i = 0; i < 4; i++) {
				int newx = w.first + dx[i], newy = w.second + dy[i];
				if (0 <= newx && newx < R && 0 <= newy && newy < C
					&& lake[newx][newy] == 'X') 
				{
					lake[newx][newy] = '.';
					waterq.push({ newx,newy });
				}
			}
		}
		
		day++;
	}

	cout << day;
}
```

이전 풀이와의 차이점 : 물에서 bfs를 따로 돌리는데, 얼음을 큐에 넣을 때 바로 물로 바꿔버려서 visited를 따로 선언할 필요 없었음.

## 내 접근 방법 고친 버전

```cpp
#include<iostream>
#include<vector>
#include<queue>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef pair<int, int> pii;

int main()
{
	fastio;

	// 얼음 녹인 뒤에 오리 한 쪽에서부터 갈 수 있는지 체크.
	// 근데 이전 체크에서 얼음이었던 곳에서부터 bfs 다시 시작함.
	int R, C;
	string s;
	cin >> R >> C;
	vector<string> lake(R);
	pii duck;
	queue<pii> iceq;

	vector<int> dx = { 1,-1,0,0 };
	vector<int> dy = { 0,0,1,-1 };

	vector<vector<bool>> visited(R, vector<bool>(C));
	vector<vector<bool>> willmelt(R, vector<bool>(C));
	for (int i = 0; i < R; i++) {
		cin >> lake[i];
	}

	// 녹일 얼음을 확인
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (lake[i][j] == 'L') { duck = { i,j }; }
			else if (lake[i][j] == 'X') {
				for (int k = 0; k < 4; k++) {
					int newx = i + dx[k];
					int newy = j + dy[k];
					if (0 <= newx && newx < R && 0 <= newy && newy < C
						&& ((lake[newx][newy] == '.') || (lake[newx][newy] == 'L'))) {
						willmelt[i][j] = true;
						iceq.push({ i,j });
						break;
					}
				}
			}
		}
	}

	bool done = false;
	int day = 0;
	queue<pii> duckq;
	duckq.push(duck);
	visited[duck.first][duck.second] = true;
	while (true)
	{
		int dd = 0;
		// 오리가 방문하지 않은 물을 전부 탐색
		while (!duckq.empty()) {
			pii d = duckq.front(); duckq.pop();
			for (int i = 0; i < 4; i++) {
				int newx = d.first + dx[i];
				int newy = d.second + dy[i];
				if (0 <= newx && newx < R && 0 <= newy && newy < C
					&& !visited[newx][newy])
				{
					if (lake[newx][newy] == '.') {
						visited[newx][newy] = true;
						duckq.push({ newx,newy });
					}
					else if (lake[newx][newy] == 'L') {
						done = true;
						break;
					}
				}
			}
			if (done) break;
		}
		if (done) break;

		// 얼음을 녹일 때 상하좌우 확인하고 다음 녹일 얼음 확인
		int iceqlen = iceq.size();
		while (iceqlen--) {
			pii ice = iceq.front(); iceq.pop();
			int icex = ice.first, icey = ice.second;
			lake[icex][icey] = '.';
			bool newduck = false;
			for (int i = 0; i < 4; i++) {
				int newx = icex + dx[i], newy = icey + dy[i];
				if (0 <= newx && newx < R && 0 <= newy && newy < C)
				{
					// 상하좌우에 오리가 방문한 물이 있다면 오리 큐에 추가
					if (visited[newx][newy] && 
						((lake[newx][newy] == '.') || (lake[newx][newy] == 'L'))) {
						newduck = true;
					}
					// 상하좌우에 아직 녹을 예정도 아닌 얼음이 있다면 녹일 예약
					else if (!willmelt[newx][newy] && lake[newx][newy] == 'X') {
						willmelt[newx][newy] = true;
						iceq.push({ newx,newy });
					}
				}
			}
			if (newduck) {
				visited[icex][icey] = true;
				duckq.push(ice);
			}
		}

		day++;
	}
	cout << day;
}
```

오리가 물에 떠있으니 오리도 물 취급을 해줬어야 했던 거. 시간 복잡도 상으로는 틀리지 않는데, 그냥 무한 루프를 돌아서 시간 초과가 떠버렸던 것.

그와 별개로 이 코드가 더 복잡.

## 다른 사람 풀이에서 배운 점

* `const int dx[] = { 0,0,1,-1 };` : 이거 쓰면 약간 더 빨라지긴 할듯. 사실상 무의미하긴 함.
* `if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue; if (visited[nx][ny]) continue;` if문 안에 감싸는 것보다 보호 구문 처리 하는게 더 낫긴 할듯
* `for (int j = 0; j < M; j++) { cin >> A[i][j];` 띄어쓰기 없다고 꼭 string으로 안 받아도 됨. cin을 char에 넣으면 알아서 한 문자만 받음.

```cpp
	while (true) {
		if (check()) {
			cout << t;
			exit(0);
		}
		waterSpread();
		t++;
	}
```

필요한 건 전역 변수로 두고, 이렇게 함수로 나눠서 작성하면 디버깅도 편하고 보기에도 편하긴 할듯. 이런 식으로 작성하는거 연습해보자.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined-1/3197.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.