[BOJ] 16000. 섬

문제

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

16000번: 섬

 

풀이

우선 flood fill을 이용하여 각 섬별로 넘버링을 한다.

같은 방법으로 0,0 구석의 물에서부터도 flood fill을 이용하여 안전한 바다를 전부 구할것이다.

flood fill을 할때, 4방향, 즉 상하좌우의 경우 인접한 바다를 모두 queue에 추가한다.

또한 추가적으로 대각선방향 4방향에서도 안전한 바다로 전파될 수 있는 바다들이 존재한다.

 

만약

#.

.#

모양처럼 대각선으로만 뚫려있고 상하로 막혀있지만, 왼쪽의 섬과 오른쪽의 섬이 서로 다른 섬이라면 사냥꾼은 두 섬에 동시에 존재할 수 없으므로, 둘 중 사냥꾼이 없는 쪽으로 빠져나올 수 있다.

따라서 대각선으로만 뚫려있어도 위의 조건에 해당한다면 queue에 추가해준다.

 

이 과정을 진행하면서 안전한 바다와 인접한 땅들을 모두 체크해주어 'O'로 바꾸고, 나머지를 'X'로 바꾸면 문제를 해결할 수 있다.

 

Time Complexity : $O(nm)$

 

코드

#include<iostream>
#include<string>
#include<queue>
#define N 2004

using namespace std;
typedef pair<int,int> pi;
string s[N];
int mp[N][N],n,m,color;
pi flag[4]={pi(1,0),pi(0,1),pi(-1,0),pi(0,-1)};
vector<char> ans;

pi operator+(const pi &x1, const pi &x2)
{
	return make_pair(x1.first+x2.first, x1.second+x2.second);
}

bool cango(pi t)
{
	return t.first>=0 && t.first<n && t.second>=0 && t.second<m;
}

void floodFillLand(pi st, int v)
{
	mp[st.first][st.second]=v;
	queue<pi> Q;
	Q.push(st);
	while(!Q.empty())
	{
		pi f = Q.front();
		Q.pop();
		for(int k=0;k<4;k++)
		{
			pi next = f+flag[k];
			vector<int> V;

			if(!cango(next) || mp[next.first][next.second]!=0) continue;

			if(s[next.first][next.second]=='#')
			{
				mp[next.first][next.second] = v;
				Q.push(next);
			}
		}
	}
}

void floodFillWater(pi st)
{
	mp[st.first][st.second]=-1;
	queue<pi> Q;
	Q.push(st);
	while(!Q.empty())
	{
		pi f = Q.front();
		Q.pop();
		for(int k=0;k<4;k++)
		{
			pi next = f+flag[k];
			if(!cango(next)) continue;
			if(mp[next.first][next.second]>0)
			{
				ans[mp[next.first][next.second]]='O';
				continue;
			}

			if(mp[next.first][next.second]==0 && s[next.first][next.second]=='.')
			{
				mp[next.first][next.second] = -1;
				Q.push(next);
			}
		}

		for(int k=0;k<4;k++)
		{
			pi next= f+flag[k]+flag[(k+1)&3];
			pi c1 = f+flag[k];
			pi c2 = f+flag[(k+1)&3];
			if(!cango(next) || s[next.first][next.second]=='#') continue;

			if(mp[next.first][next.second]!=-1 && mp[c1.first][c1.second]>0
				&& mp[c2.first][c2.second]>0 && mp[c1.first][c1.second]!=mp[c2.first][c2.second])
			{
				mp[next.first][next.second] = -1;
				Q.push(next);
			}
		}
	}
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>s[i];

	color=0;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		if(mp[i][j] || s[i][j]=='.') continue;
		floodFillLand(make_pair(i,j),++color);
	}

	ans.resize(color+1,'X');
	floodFillWater(make_pair(0,0));

	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		if(s[i][j]=='.')continue;
		s[i][j] = ans[mp[i][j]];
	}

	for(int i=0;i<n;i++) cout<<s[i]<<"\n";
}