Flood fill (BOJ 3197 백조의 호수)

문제

백조의 호수

알고리즘

1. 백조의 움직임과 얼음의 상태 변화 로직을 분리 (moveSwan, melting)
2. moveSwan()
   2-1. 백조 중 하나의 좌표를 swim(queue)에 삽입
   2-2. 물의 좌표를 swim에 삽입하며 BFS 진행
   2-3. 얼음을 만나면 nextSwim(queue)에 삽입 후 continue
   2-4. 다른 백조의 좌표를 만나면 리턴 후 결과 값(ret) 출력
3. melting()
   3-1. 입력 시 물의 좌표를 water(queue)에 삽입
   3-2. 얼음을 만나면 해당 좌표를 물로 바꿔준 후 nextWater(queue)에 삽입
4. 기존의 빈 queue(swim, water)를 nextQueue(nextSwim, nextWater)로 업데이트
5. 다른 백조를 만날 때까지 ret을 증가시키며 1~4번 과정을 반복

코드

#include<bits/stdc++.h>

using namespace std;

int R,C, ret = 0;

pair<int,int> swan;

queue<pair<int,int>> swim;
queue<pair<int,int>> nextSwim;
queue<pair<int,int>> water;
queue<pair<int,int>> nextWater;
//vector<pair<int,int>> melted;

vector<pair<int,int>> moveTo = {
	{1,0}, {0,1},
	{-1,0}, {0,-1}
};


char Map[1504][1504];
int visited[1504][1504] = {0,};
int visitedSwan[1504][1504] = {0,};


bool rangeCheck(int y, int x){
	return 0<=y && y<R && 0<=x && x<C;
}

void QClear(queue<pair<int, int>>& que){
	queue<pair<int,int>> empty;
	swap(que, empty);
}

void input(){
	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] == '.' || Map[i][j] == 'L'){
				visited[i][j] = 1;
				water.push({i,j});
				
				if(Map[i][j] == 'L') swan = make_pair(i,j);
			}
		}
	}
	
	swim.push(swan);
	visitedSwan[swan.first][swan.second] = 1;
}

void melting(){
	pair<int,int> now;
	while(!water.empty()){
		now = water.front();
		water.pop();
		
		for(int i=0; i<moveTo.size(); i++){
			int nextY = now.first  + moveTo.at(i).first;
			int nextX = now.second + moveTo.at(i).second;
			
			if(!rangeCheck(nextY, nextX)) continue;
			if(visited[nextY][nextX]) continue;
			
			if(Map[nextY][nextX] == 'X'){
				visited[nextY][nextX] = 1;
				nextWater.push({nextY, nextX});
				Map[nextY][nextX] = '.';
			}
		}
	}
}

bool moveSwan(){
	pair<int,int> now;
	while(!swim.empty()){
		now = swim.front();
		swim.pop();
			
		for(int i=0; i<moveTo.size(); i++){
			int nextY = now.first  + moveTo.at(i).first;
			int nextX = now.second + moveTo.at(i).second;
				
			if(!rangeCheck(nextY,nextX)) continue;
			if(visitedSwan[nextY][nextX]) continue;

			visitedSwan[nextY][nextX] = 1;
				
			if(Map[nextY][nextX] == 'X') 	  nextSwim.push({nextY, nextX});
			else if(Map[nextY][nextX] == '.') swim.push({nextY,nextX});
			else if(Map[nextY][nextX] == 'L') return true;
		}
			
	}
	return false;
}




void run(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
	input();
	
	while(true){
		if(moveSwan()) break;
		melting();
		water = nextWater;
		swim = nextSwim;
		QClear(nextSwim);
		QClear(nextWater);
		ret++;
	}
	
	cout << ret;
		
	return;
}


int main(){

	run();
		
	return 0;
} 

후기

숨바꼭질5에 이은 flood fill 문제

첫 시도에선 BFS(백조)와 DFS(물)로 탐색하다 시간초과 러쉬를 맞고(...)
결국 질문 게시판과 강의를 참고해 flood fill 알고리즘으로 작성

해당 알고리즘에 익숙치 않아서 그런지 적용 사례와 사고 흐름이 아직은 낯설다.
이젠 징글징글할 정도로 자주 짠 BFS랑 DFS처럼
유사한 문제들을 많이 풀어서 체화시켜야 할 듯