백준 알고리즘 풀이 3197번 - 백조의 호수

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

3197번: 백조의 호수

 

---

- BFS 문제

다음번에 탐색할 위치와, 얼음을 녹일 위치를 저장하는 문제.

알고리즘

---

큐를 총 4개 준비한다. 

현재 백조의 bfs를 탐색하는 swanQ

1일뒤 백조가 bfs를 탐색할 swanNQ

현재 얼음을 녹이는 bfs를 탐색할 iceQ

1일뒤 얼음을 녹이는 bfs를 탐색할 iceNQ

 

1. 백조가 진행하는 첫번째 bfs를 구성한다. 

처음 실행이라면, 백조의 위치에서 시작하는 bfs를 구성한다. 이때, 백조가 움직이면서, 얼음을 만난다면, 다음에 탐색을 하기위해 swanNQ에 넣어준다. 얼음이 아니라 다른 백조라면 탐색을 종료. 물을 만난다면, 현재 탐색을 위해 현재 좌표를 swanQ에 넣어준다.

2. 얼음을 녹이는 두번째 bfs를 구성한다.

처음 실행이라면, 물이 있는 경우 iceQ에 해당 좌표를 넣어준다. bfs를 돌리면서 옆에 물이라면 iceQ에 넣어주고, 물이 아닌 얼음이라면, 다음 탐색을 위해 iceNQ에 넣어준다. 그리고 해당 좌표는 물로 바꿔준다.

3. 진행

백조가 진행하는 bfs를 돌리고, 다른 백조를 만나지 못했다면 얼음을 녹인다. 1일이 지났음을 표기한다.

다른 백조를 만날때까지 반복..

---

 

소스코드

---

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

char map[1501][1501];
queue<pair<int,int> > willVisitQ;
queue<pair<int,int> > q;
queue<pair<int,int> > iceQ;
queue<pair<int,int> > nextIceQ;

bool isVisited[1501][1501];
int sizeX,sizeY;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
pair<int,int> swan;

// 하루 지나면 얼음 녹는거 생각 -> bfs로 얼음을 녹인다
// 하루 지나면 녹을 얼음이 오리가 가는 경로에 있다면 -> 다음 오리가 탐색시작할 위치는 거기임
bool swan_bfs()
{
	while(!q.empty()){
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			int nextX = nowX + dx[i];
			int nextY = nowY+dy[i];
			if(nextX<=0 || nextX>sizeX || nextY<=0 || nextY>sizeY || isVisited[nextY][nextX]){
				continue;
			}
			if(map[nextY][nextX]=='X') {
				willVisitQ.push(make_pair(nextX,nextY));
				// cout<<"다음에 탐사할 영역 X: "<<nextX<<"y : "<<nextY<<endl;
				isVisited[nextY][nextX] = true;
			}
			else if(map[nextY][nextX]=='.'){
				q.push(make_pair(nextX,nextY));
				isVisited[nextY][nextX] = true;
			}
			else if(map[nextY][nextX]=='L'){
				while(!q.empty()) q.pop();
				return true;
			}
		}
	}
	return false;
}

void melt_bfs()
{
	int count = 0;
	while(!iceQ.empty()){
		int nowX = iceQ.front().first;
		int nowY = iceQ.front().second;
		iceQ.pop();
		for(int i=0;i<4;i++){
			int nextX = dx[i]+nowX;
			int nextY = dy[i]+nowY;
			if(nextX<= 0 || nextX>sizeX || nextY<=0 || nextY>sizeY || map[nextY][nextX]=='.'){
				continue;
			}
			//다음에 녹일 얼음
			if(map[nextY][nextX]=='X'){
				// cout<<"다음에 녹일 얼음 X: "<<nextX<<"y : "<<nextY<<endl;
				count++;
				map[nextY][nextX] = '.';
				nextIceQ.push(make_pair(nextX,nextY));
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	sizeX = 100;
	sizeY =100;
	cin>>sizeY>>sizeX;
	for(int i=1;i<=sizeY;i++){
		for(int j=1;j<=sizeX;j++){
			cin>>map[i][j];
			isVisited[i][j] = false;
			if(map[i][j]=='L'){
				swan.first = j; //현재 오리의 x좌표
				swan.second = i; // 현재 오리의 y좌표
			}if(map[i][j]=='.' || map[i][j]=='L'){
				iceQ.push(make_pair(j,i));
			}
		}
	}
	
	
	int ans =0;
	willVisitQ.push(make_pair(swan.first,swan.second));
	isVisited[swan.second][swan.first] = true;
	while(!swan_bfs()){
		q= willVisitQ;
		melt_bfs();
		iceQ=nextIceQ;
		// cout<<iceQ.size()<<endl;
		while (!nextIceQ.empty()) nextIceQ.pop();
    	while (!willVisitQ.empty()) willVisitQ.pop();
		ans++;
	}
	cout<<ans;
	return 0;
}

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)