3197 백조의 호수

알고리즘(구현)

처음 방법
	1. 한 백조에서 BFS 실시하여 다른 백조를 만날 수 있는지 검사
	2. 전체 맵을 검사해서 녹일 수 있는 걸 녹임
	3. day 추가하고 다시 1부터
	-> 시간이 너무 걸림. 특히 맵 초기화하는 부분이 많이 걸림
두번째 방법
	1. 1번은 유지
	2. 녹을 수 있는 얼음만 저장한 q에서 얼음을 하나씩 꺼내서 녹이고, 주변에 검사되지않은 얼음이 있으면 따로 저장
		-> q가 끝나면 따로 저장한 얼음을 q에 복사
	3. day추가하고 다시 1부터
	-> 또 시간초과
세번째 방법
	1. 백조가 갈수있는 칸을 전부 각각 L, l 로 바꿈
	2. 얼음과 L, l의 경계선을 q에 저장
	3. 2방법으로 다 녹이고 나서, q에 있는 칸을 하나씩 꺼내고 주변을 검사하여 또 L, l 로 바꾼다
	4. 바꾸는데 다른 문자를 발견하면 스탑 후 출력
	-> 코드가 너무 복잡하여 헷갈림. 어딘가 잘못됨
네번째 방법
	1. 백조가 갈 수 잇는 칸을 전부 각각 L,l 로 바꿈
	2. 얼음을 한칸 녹일 때마다 주변을 검사하여 적절한 문자로 치환
		주변에 (L과 l) 두개 있을 때
			-> 만난 것 -> 출력 후 종료
		주변에 L 또는 l 만 있을 때
			-> 만나지 않음. 그 얼음칸을 중심으로 BFS를 실시하여 갈 수 있는 모든 칸을 L 또는 l로 바꿈
		주변에 L, l 둘다 없을 때
			-> 그냥 . 으로 치환
	-> 통과

코드

#include <iostream>
#include <vector>
#include <list>
#define MAX_WIDTH 1500
 
using namespace std;
 
typedef struct Location {
	int row;
	int col;
} Location;
 
int row, col, todayLength;
Location bird1, bird2;
Location meltToday[MAX_WIDTH*MAX_WIDTH];
char map[MAX_WIDTH][MAX_WIDTH];
bool visit[MAX_WIDTH][MAX_WIDTH], meltVisit[MAX_WIDTH][MAX_WIDTH];
list<Location> q;
 
bool init();
void initBird(Location bird, char c);
bool meltIce();
bool checkBird(int r, int c);
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> row >> col;
 
	bool check = false;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'L') {
				if (!check) {
					bird1.row = i;
					bird1.col = j;
					check = true;
				}
				else {
					bird2.row = i;
					bird2.col = j;
					map[i][j] = 'l';
				}
			}
		}
	}
 
	if (init()) {
		cout << 0;
		return 0;
	}
 
	int day = 1;
	while (true) {
		cout << endl;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++)
				cout << map[i][j];
			cout << endl;
		}
		cout << endl;
		if (meltIce()) {
			cout << day;
			break;
		}
		day++;
	}
}
 
bool init() {
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (map[i][j] == 'X') {
				if (i > 0 && map[i - 1][j] != 'X') {
					meltToday[todayLength++] = { i, j };
					meltVisit[i][j] = true;
				}
				else if (j < col - 1 && map[i][j + 1] != 'X') {
					meltToday[todayLength++] = { i, j };
					meltVisit[i][j] = true;
				}
				else if (i < row - 1 && map[i + 1][j] != 'X') {
					meltToday[todayLength++] = { i, j };
					meltVisit[i][j] = true;
				}
				else if (j > 0 && map[i][j - 1] != 'X') {
					meltToday[todayLength++] = { i, j };
					meltVisit[i][j] = true;
				}
			}
		}
	}
 
	initBird(bird1, 'L');
	if (map[bird2.row][bird2.col] == 'L')
		return true;
	initBird(bird2, 'l');
	return false;
}
 
void initBird(Location bird, char c) {
	q.push_back({ bird.row, bird.col });
	visit[bird.row][bird.col] = true;
 
	while (!q.empty()) {
		Location temp = q.front();
		q.pop_front();
		map[temp.row][temp.col] = c;
 
		if (temp.row > 0 && !visit[temp.row - 1][temp.col] && map[temp.row - 1][temp.col] != 'X') {
			q.push_back({ temp.row - 1, temp.col });
			visit[temp.row - 1][temp.col] = true;
		}
		if (temp.row < row - 1 && !visit[temp.row + 1][temp.col] && map[temp.row + 1][temp.col] != 'X') {
			q.push_back({ temp.row + 1, temp.col });
			visit[temp.row + 1][temp.col] = true;
		}
		if (temp.col > 0 && !visit[temp.row][temp.col - 1] && map[temp.row][temp.col - 1] != 'X') {
			q.push_back({ temp.row, temp.col -1 });
			visit[temp.row][temp.col - 1] = true;
		}
		if (temp.col < col - 1 && !visit[temp.row][temp.col + 1] && map[temp.row][temp.col + 1] != 'X') {
			q.push_back({ temp.row, temp.col + 1});
			visit[temp.row][temp.col + 1] = true;
		}
	}
}
 
bool meltIce() {
	int index = 0;
	vector<Location> q;
 
	while (index < todayLength) {
		if (checkBird(meltToday[index].row, meltToday[index].col))
			return true;
 
		if (meltToday[index].row > 0 && map[meltToday[index].row - 1][meltToday[index].col] == 'X' && !meltVisit[meltToday[index].row-1][meltToday[index].col] ) {
			q.push_back({ meltToday[index].row - 1, meltToday[index].col });
			meltVisit[meltToday[index].row - 1][meltToday[index].col] = true;
		}
 
		if (meltToday[index].col < col - 1 && map[meltToday[index].row][meltToday[index].col + 1] == 'X' && !meltVisit[meltToday[index].row][meltToday[index].col + 1]) {
			q.push_back({ meltToday[index].row, meltToday[index].col + 1 });
			meltVisit[meltToday[index].row][meltToday[index].col + 1] = true;
		}
 
		if (meltToday[index].row < row - 1 && map[meltToday[index].row + 1][meltToday[index].col] == 'X' && !meltVisit[meltToday[index].row + 1][meltToday[index].col]) {
			q.push_back({ meltToday[index].row + 1, meltToday[index].col });
			meltVisit[meltToday[index].row + 1][meltToday[index].col] = true;
		}
 
		if (meltToday[index].col > 0 && map[meltToday[index].row][meltToday[index].col - 1] == 'X' && !meltVisit[meltToday[index].row][meltToday[index].col - 1]) {
			q.push_back({ meltToday[index].row, meltToday[index].col - 1 });
			meltVisit[meltToday[index].row][meltToday[index].col - 1] = true;
		}
 
		index++;
	}
	todayLength = 0;
 
	//넣기
	for (int i = 0; i < q.size(); i++)
		meltToday[todayLength++] = q[i];
 
	return false;
}
 
bool checkBird(int r, int c) {
	bool checkL = false, checkl = false;
	if (r > 0 && map[r - 1][c] == 'L')
		checkL = true;
	else if (r < row - 1 && map[r + 1][c] == 'L')
		checkL = true;
	else if (c > 0 && map[r][c - 1] == 'L')
		checkL = true;
	else if (c < col - 1 && map[r][c + 1] == 'L')
		checkL = true;
 
	if (r > 0 && map[r - 1][c] == 'l')
		checkl = true;
	else if (r < row - 1 && map[r + 1][c] == 'l')
		checkl = true;
	else if (c > 0 && map[r][c - 1] == 'l')
		checkl = true;
	else if (c < col - 1 && map[r][c + 1] == 'l')
		checkl = true;
 
	if (checkL && checkl)
		return true;
	else if (checkL) {
		map[r][c] = 'L';
		initBird({ r,c }, 'L');
		if (map[bird2.row][bird2.col] == 'L')
			return true;
	}
	else if (checkl) {
		map[r][c] = 'l';
		initBird({ r,c }, 'l');
		if (map[bird1.row][bird1.col] == 'l')
			return true;
	}
	else
		map[r][c] = '.';
	return false;
}