[백준/BOJ] 3197번 백조의 호수 (C++)

www.acmicpc.net/problem/3197

3197번: 백조의 호수

어려운 BFS 문제, 푸는데 3~4시간 걸렸다. 근데 시간이 이정도로 오래 걸린건 어려워서 그런게 아니라 "map[nx][ny] = '.';" 요 부분을 "map[nx][ny] == '.';" 이렇게 써가지구 자꾸 답이 이상하게 나왔다. SIBAL (다시풀기)

 

풀이는 일반적인 BFS 방법을 사용하면 시간초과가 발생한다. BFS 탐색에서의 시간을 줄이기 위해서 백조를 탐색할 때 기존에 체크했던 배열을 그대로 두고, 큐를 갱신해가면서 빙하가 녹아서 물이 된 부분만 탐색할 수 있게끔 하여 시간을 단축할 수 있다.

 

/* 정답 코드 */

#include <iostream>
#include <vector>
#include <queue>
#define MAX 1501
using namespace std;

char map[MAX][MAX];
bool visit[MAX][MAX];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0 ,1};
vector<pair<int, int> > v;
queue<pair<int, int> > sq, wq;
int r, c, answer;

// 백조끼리 만날 수 있는지 확인하는 BFS
bool isPossible() {
	queue<pair<int, int> > tmp;
	while (!sq.empty()) {
		int x = sq.front().first;
		int y = sq.front().second;
		sq.pop();
		
		// 백조를 만나면 true를 리턴 
		if(x == v[1].first && y == v[1].second) return true;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= r || ny < 0 || ny >= c || visit[nx][ny]) continue;
			if (map[nx][ny] == 'X') tmp.push({nx, ny}); // 물에 인접한 빙하를 만나므로 다음에 탐색하기 위해 임시 큐에 저장  
			else sq.push({nx, ny});
			visit[nx][ny] = true;
		}
	}
	
	// 아까 임시 큐에 저장된 빙하의 위치(다음날 녹을 빙하)를 기존 큐에 저장 
	// 처음부터 탐색하지 않아서 시간을 아낄 수 있음  
	sq = tmp;
	// 백조를 만날 수 없다면 false를 리턴  
	return false;
}

// 녹는 빙하 찾는 BFS 
void meltIce() {
	// 기존 물의 영역만 탐색
	int size = wq.size();
	while (size--) {
		int x = wq.front().first;
		int y = wq.front().second;
		wq.pop();
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			// 기존 물에 빙산이 인접해 있으면 녹이고, 다음에 탐색할 수 있게 큐에 넣어줌  
			if (map[nx][ny] == 'X') {
				map[nx][ny] = '.'; // SIBAL
				wq.push({nx, ny});
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>r>>c;
	
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin>>map[i][j];
			if (map[i][j] == 'L') v.push_back({i, j}); // 백조의 위치를 벡터에 저장
			if (map[i][j] != 'X') wq.push({i, j}); // 물의 위치를 큐에 저장 
		}
	}
	
	sq.push(v[0]);
	visit[v[0].first][v[0].second] = true;
	
	while (1) {
		if(isPossible()) {
			cout<<answer;
			break;
		}
		
		meltIce(); // 빙하가 녹는다. 
		answer++; // 하루가 지난다.  
	}
}

 

2회차

#include<bits/stdc++.h>
#define f first
#define s second
#define lp1(i, x, n) for(int i = x; i <= n; i++)
using namespace std;
typedef long long ll;

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

int t, n, m, k, sx, sy, ex, ey, x, y, z, answer, L, R, _x1, _x2, _y1, _y2, flag;
char area[1501][1501], cpy[1501][1501];
int visited[1501][1501];
queue<pair<int, int>> ice, q;

bool BFS() {
	queue<pair<int, int>> tmp;
	while(!q.empty()) {
		tie(x, y) = q.front();
		q.pop();
		if(x == _x2 && y == _y2) return true;
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] == 1) continue;
			if(area[nx][ny] == 'X') tmp.push({ nx, ny });
			else q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
	q = tmp;
	return false;
}

void melt() {
	queue<pair<int, int>> tmp;
	while(!ice.empty()) {
		bool isMelted = false;
		tie(x, y) = ice.front();
		ice.pop();
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if(area[nx][ny] == '.') {
				isMelted = true;
				cpy[x][y] = '.';
				break;
			}
		}
		if(!isMelted) tmp.push({ x, y });
	}
	ice = tmp;
}

int main() {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		for(int j  = 0; j < m; j++) {
			cin >> area[i][j];
			if(area[i][j] == 'L') {
				if(!flag) _x1 = i, _y1 = j, flag = 1;
				else _x2 = i, _y2 = j;
			} else if(area[i][j] == 'X') ice.push({ i, j }); 
		}
	}
	
	q.push({ _x1, _y1 });
	visited[_x1][_y1] = 1;
	
	while(1) {
//		for(int i = 0; i < n; i++) {
//			for(int j = 0; j < m; j++) {
//				cout << area[i][j] << " ";
//			}
//			cout << "\n";
//		}
//		cout << "\n";
		if(BFS()) break;
		memcpy(cpy, area, sizeof(area));
		melt();
		memcpy(area, cpy, sizeof(cpy));
		answer++;
	}
	cout << answer;
}