BOJ 3197 백조의 호수 / C++

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

3197번: 백조의 호수

백준 온라인저지 3197번 백조의 호수 문제입니다.

 

아이디어

문제 자체는 백준 온라인저지에 있는 치즈, 토마토와 같은 BFS 문제들과 비슷한데 조금 다른점은 얼음이 녹는데서 그치지 않고 백조가 만날 수 있는지를 확인을 해야합니다. BFS가 얼음녹이는 부분과 백조 만나는 부분 총 2번을 전체탐색 진행이 되어야하는데 플레티넘 문제에서 이런 복잡도는 말이 안된다고 생각했고, 탐색마다 변화하는 부분만 처리  할 수 있는 방법을 고민이 필요합니다. 다른 분들의 코드를 참고했고 문제를 푸는데만 그치지않고 최적화에 대해 다시 생각해 볼 수 있는 문제였습니다.

 

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

class Point {
public:
	int y, x;
	Point(int a, int b) {
		y = a;
		x = b;
	}
	Point(){}
};

int R, S;
int days = 0;
vector<vector<char>> field;
vector<vector<bool>> visited;
queue<Point> water;
queue<Point> nextWater;
queue<Point> area;
queue<Point> nextArea;

int mx[4] = { 0,0,1,-1 };
int my[4] = { 1,-1,0,0 };




void input() {
	cin >> R >> S;
	field = vector<vector<char>>(R, vector<char>(S, '.'));
	visited = vector<vector<bool>>(R, vector<bool>(S, false));
	Point swan;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < S; j++) {
			cin >> field[i][j];
			if (field[i][j] == 'L') {
				swan = Point(i, j);
			}
			if (field[i][j] != 'X') {
				water.push(Point(i, j));
			}
		}
	}
	area.push(swan);
}

void meltIce() {
	while (!water.empty()) {
		Point p = water.front();
		water.pop();
		for (int i = 0; i < 4; i++) {
			int y = p.y + my[i];
			int x = p.x + mx[i];
			if (y >= R || y < 0 || x >= S || x < 0) continue;
			if (field[y][x] == 'X') {
				field[y][x] = '.';
				nextWater.push(Point(y, x));
				//break; 여기 때문에 5%에서 틀림 - https://www.acmicpc.net/board/view/94425
			}
		}
	}
}

bool findSwan() {
	while (!area.empty()) {
		Point cur = area.front();
		visited[cur.y][cur.x] = true;
		area.pop();
		for (int i = 0; i < 4; i++) {
			int y = my[i] + cur.y;
			int x = mx[i] + cur.x;
			if (y >= R || y < 0 || x >= S || x < 0) continue;
			if (visited[y][x]) continue;
			visited[y][x] = true;
			if (field[y][x] == 'X') {
				nextArea.push(Point(y, x));
			}
			else if (field[y][x] == '.') {
				area.push(Point(y, x));
			}
			if (field[y][x] == 'L') return true;
		}


	}
	return false;
}

void solution() {
	while (true) {		
		if (findSwan()) break;		
		meltIce();
		area = nextArea;
		water = nextWater;
		nextArea = queue<Point>();
		nextWater = queue<Point>();
		days++;
	}
	cout << days;
}

int main(void) {
	input();
	solution();
}
//https://www.acmicpc.net/problem/3197