백준 3197 C++

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

3197번: 백조의 호수

 

처음으로 플레를 혼자서 풀어서 성공했다.

 

처음에 그냥 일반적으로 빙판이 녹는걸 생각해서 시간초과가 나타났다.

치즈와 같은 문제에서는 이렇게하면 풀렸기 때문이다.

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1500;
bool meet = false;
int r, c;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };

vector<pair<int, int>> backs;		//2개만 들어옴
vector<pair<int, int>> melt;
int lake[MAX + 10][MAX + 10];
int visited[MAX + 10][MAX + 10];

void dfs(int y, int x, bool isBack){
	//cout << "y : " << y << "  x : " << x << "\n";
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
		if (visited[ny][nx]) continue;

		if (lake[ny][nx] == '.') {
			visited[ny][nx] = 1;
			dfs(ny, nx, isBack);
		}
		
		if (lake[ny][nx] == 'X') {
			visited[ny][nx] = 1;
			melt.push_back({ ny, nx });
		}

		if (isBack && ny == backs[1].first && nx == backs[1].second) {
			meet = true;
			return;
		}
	}
}

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

	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			char ch; cin >> ch;
			lake[i][j] = ch;
			if (ch == 'L') backs.push_back({ i, j });
		}
	}

	int count = 0;
	while (!meet)
	{
		dfs(backs[0].first, backs[0].second, true);

		//cout << "Come\n";
		if (meet) {
			break;
		}

		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (!visited[i][j] && lake[i][j] == '.') {		//방문하지 않고 .으로 되어 있어서 시작점이 될 수 있는 곳이라면
					//visited[i][j] = 1;
					dfs(i, j, false);
				}
			}
		}

		for (auto i : melt) {
			lake[i.first][i.second] = '.';		//빙판을 녹임
		}

		count++;
		
		fill(&visited[0][0], &visited[0][0] + 1510 * 1510, 0);
		//cout << "\nvisited initalize \n";
	}

	cout << count;
}

이게 정답처리가 안되서 맞는 코드인지 모르겠지만 일단 시간초과를 벗어나야겠다는 생각을 했고

빙판의 가장자리만 저장해서 녹이고 거기서부터 DFS 시작하고 다시 가장자리만 저장해서 가장자리만 녹이고 DFS를 시작하는 형식으로 반복 횟수를 줄였다.

또한 백조가 움직이는 것도 동일한 방식으로 백조가 빙판에서 막힌 부분에서 빙판이 녹고 다시 DFS시작을 반복하였다.

그랬더니 시간초과를 벗어나 성공하였다.

 

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1500;
int r, c; int dayCount= 0;
bool findBack = false;

int lake[MAX + 10][MAX + 10];
int visited[MAX + 10][MAX + 10];
int Lvisited[MAX + 10][MAX + 10];		//백조가 지나온 길을 visited로 정의한다.

vector<pair<int, int>> backs;			//백조의 위치를 저장한다.
vector<pair<int, int>> LBolcks[2];		//백조의 길을 막은 빙판을 저장한다.
vector<pair<int, int>> Xs1;
vector<pair<int, int>> Xs2;

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


void XDFS(int y, int x, bool isPushOne) {		//가장자리 빙판 체크용 DFS
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= r || nx >= c)	continue;	//범위 벗어난것이기에 continue;
		if (visited[ny][nx]) continue;		//방문한건 넘긴다.

		if (lake[ny][nx] == '.' || lake[ny][nx] == 'L') {
			//물이라서 더 퍼져나갈 수 있다면
			visited[ny][nx] = 1;
			XDFS(ny, nx, isPushOne);
		}
		else if (lake[ny][nx] == 'X') {
			visited[ny][nx] = 1;
			if (isPushOne) {
				Xs1.push_back({ ny,nx });		//가장 가장자리의 빙판을 저장한다. -> dayCount(0이면 0번이 지난 날)날의 가장자리 빙판을 저장한다. 
			}
			else {
				Xs2.push_back({ ny, nx });
			}
		}
	}
}

void LMove(int y, int x, bool isZeroPush) {		//백조의 DFS
	//cout << "LMove   Y: " << y << "  X : " << x << "\n";
	Lvisited[y][x] = 1;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= r || nx >= c)	continue;	//범위 벗어난것이기에 continue;
		if (Lvisited[ny][nx] || findBack) continue;		//방문한것을 넘기고 백조를 찾았을 때도 굳이 할 필요가 없다.

		if (lake[ny][nx] == '.') {
			//백조가 물을 만나 더 나아갈 수 있다면
			Lvisited[ny][nx] = 1;
			LMove(ny, nx, isZeroPush);
		}
		else if (lake[ny][nx] == 'X') {
			//백조가 빙판을 만나 더 이상 나아갈 수 없다면
			Lvisited[ny][nx] = 1;
			if (isZeroPush) {
				LBolcks[0].push_back({ny, nx});		//백조가 막힌 부분을 저장해서 여기서부터  시작할 수 있도록 한다.
			}
			else {
				LBolcks[1].push_back({ ny, nx });
			}
		}
		else if (lake[ny][nx] == 'L') {
			findBack = true;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	fill(&visited[0][0], &visited[0][0] + (MAX + 10) * (MAX + 10), 0);
	fill(&Lvisited[0][0], &Lvisited[0][0] + (MAX + 10) * (MAX + 10), 0);

	cin >> r >> c;

	for (int i = 0; i < r; i++) {		//lkae에 입력 받는다.
		for (int j = 0; j < c; j++) {
			char ch; cin >> ch;
			lake[i][j] = ch;

			if (ch == 'L') {
				backs.push_back({ i, j });		//백조의 위치를 저장한다.
			}
		}
	}

	//LBolcks.push_back({ backs[0].first, backs[0].second });	
	//cout << "Pushed  Y: " << backs[0].first << "  X: " << backs[0].second;

	LMove(backs[0].first, backs[0].second, true);

	if (findBack) {
		cout << dayCount;
		return 0;
	}

	for (int i = 0; i < r; i++) {		
		for (int j = 0; j < c; j++) {
			if (!visited[i][j] && lake[i][j] != 'X') {
				//방문하지 않았고 빙판이 아니라면 XDFS를 돌린다.
				XDFS(i, j, true);		//Xs1에 Push한다.
			}
		}
	}
	

	while (!findBack) {
		//cout << "Day Count : " << dayCount << "\n";
		dayCount++;		//하루가 지나고
		//빙판이 녹고 다시 가장자리를 찾는다.
		if (!Xs1.empty()) {
			for (auto i : Xs1) {
				lake[i.first][i.second] = '.';
			}
			for (auto i : Xs1) {
				XDFS(i.first, i.second, false);
			}
			Xs1.clear();
		}
		else {
			for (auto i : Xs2) {
				lake[i.first][i.second] = '.';
			}
			for (auto i : Xs2) {
				XDFS(i.first, i.second, true);
			}
			Xs2.clear();
		}

		//빙판이 녹고 백조를 막은 부분에서 백조가 다시 출발한다.
		//계속 추가되서 에러가 발생한다.

		if (!LBolcks[0].empty()) {
			for (auto i : LBolcks[0]) {
				//cout << "LBlock Size : " << LBolcks.size();
				LMove(i.first, i.second, false);
			}
			LBolcks[0].clear();
		}
		else {
			for (auto i : LBolcks[1]) {
				//cout << "LBlock Size : " << LBolcks.size();
				LMove(i.first, i.second, true);
			}
			LBolcks[1].clear();
		}
		//위에 작업이 끝나면 백조를 막은 빙판을 다시 LBlock에 저장 OR 백조를 만난다.
	}

	cout << dayCount;

}

 

다시 풀어봤는데 위 코드보단 이게 더 깔끔해보인다.

#include <bits/stdc++.h>

using namespace std;

int r, c, dateCount = 0; bool findBack = false;
int BackVisited[1510][1510];
int WaterVisited[1510][1510];
char lake[1510][1510];

pair<int, int> Backjo;
vector<pair<int, int>> waterList;
vector<pair<int, int>> meltList;
vector<pair<int, int>> repeatMeltList;
vector<pair<int, int>> backBlockList;
vector<pair<int, int>> repeatBlockList;


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

void FindBack(int y, int x) {
	if (findBack) return;

	//cout << "y : " << y << "  x: " << x << "\n";
	if (BackVisited[y][x]) return;
	BackVisited[y][x] = 1;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
		if (BackVisited[ny][nx]) continue;
		//cout << "In ny: " << ny << "  nx : " << nx << "\n";
		if (lake[ny][nx] == '.') {
			//cout << "find ny: " << ny << "  nx : " << nx << "\n";
			FindBack(ny, nx);
		}
		else if (lake[ny][nx] == 'L') {
			findBack = true;
		}
		else if (lake[ny][nx] == 'X') {
			backBlockList.push_back({ny, nx});
		}
	}
}

void FindMeltX(int y, int x) {
	WaterVisited[y][x] = 1;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
		if (WaterVisited[ny][nx]) continue;

		WaterVisited[ny][nx] = 0;
		if (lake[ny][nx] == '.' || lake[ny][nx] == 'L') {
			FindMeltX(ny, nx);
		}
		else {
			meltList.push_back({ ny, nx });
		}
	}
}

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

	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			char ch; cin >> ch;
			lake[i][j] = ch;

			if (ch == 'L') {
				Backjo = make_pair(i, j);			//백조 위치 저장
				waterList.push_back({ i,j });
			}
			else if (ch == '.') waterList.push_back({ i, j });
		}
	}

	while (!findBack) {
		if (backBlockList.empty()) {
			FindBack(Backjo.first, Backjo.second);
		}
		else {
			repeatBlockList = backBlockList;
			backBlockList.clear();
			for (auto i : repeatBlockList) {
				if (BackVisited[i.first][i.second]) continue;
				FindBack(i.first, i.second);
			}
		}
		if (findBack) break;

		//돌렸는데 못찾음
		//그럼 빙판이 녹아야겠지
		// 
		//녹을 빙판을 찾는다.
		if (meltList.empty()) {
			for (auto i : waterList) {
				if (WaterVisited[i.first][i.second]) continue;
				FindMeltX(i.first, i.second);
			}
		}
		else {
			repeatMeltList = meltList;
			meltList.clear();
			for (auto i : repeatMeltList) {
				if (WaterVisited[i.first][i.second]) continue;
				FindMeltX(i.first, i.second);
			}
		}
	

		//녹인다.
		for (auto i : meltList) {
			lake[i.first][i.second] = '.';
		}

		dateCount++;
	}

	cout << dateCount;

}