청정알고리즘

문제

https://www.acmicpc.net/problem/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";
}

문제

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

풀이

한 줄을 입력 받아서 공백 뒤의 문자가 맨 앞 문자와 전부 같은지 체크한다.

Time Complexity : $O(|S|)$

코드

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

int main() {
	while (1) {
		string s;
		int c=1;
		char x;
		getline(cin, s,'\n');
		if (s[0] == '*') break;

		for(int i=0;i<s.length();i++) if(s[i]>='A' && s[i]<='Z') s[i]=s[i]-'A'+'a';
		x=s[0]>='a'?s[0]-'a'+'A':s[0];
		for(int i=1;c!=0 && i<s.length();i++)
		{
			if(s[i-1]==' ')
			{
				if(s[i]==s[0]) continue;
				c=0;
			}
		}
		cout<<(c?"Y\n":"N\n");
	}
}

문제

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

풀이

Dynamic Programming과 DFS spanning tree에 대한 지식 모두를 요하는 문제라 어려울 수 있다.

우선 주어진 입력으로 주어지는 방향그래프가 어떤 모양일지 생각해보자.

주어진 그래프는 $n$개의 vertex와 $n$개의 edge로 이루어져 있다.

따라서 connected component 끼리 나눠도 각각의 component에 존재하는 vertex와 edge의 개수는 같다.

따라서 이 1개의 component에 대해서만 확인해 보자.

한 component는 $k$개의 vertex와 edge로 이루어져있는데, 이는 즉 DFS spanning tree를 만들면 남는 edge가 1개가 생기고 이 edge를 제거하면 전체 그래프는 tree가 된다는 것이다.

즉, 한개의 component는 중심이 되는 cycle이 하나가 존재하고, 이 cycle에 여러개의 tree가 달라붙어 있는 모양을 가지게 된다. 다음은 component의 예시이다.

전체 component를 색칠하는 경우의 수는 (사이클을 색칠하는 경우의 수) * (트리 부분을 색칠하는 경우의 수)이다.

따라서, 이 각각을 구한다면 원하는 경우의 수를 구할 수 있다.

우선 사이클 부분의 경우의 수를 구해보자.

$dp(n,k)=$($n$개의 칸에 $k$가지 색으로 칠할 때, 이웃한 색깔을 다르게 칠하면서, 첫번째 칸과 $n$번째 칸을 다르게 칠하는 경우의 수)

이 $dp$에 대한 점화식을 구하기 위해서 다음과 같이 경우를 나눠보자.

case 1) 1번 노드의 색깔과 $n-1$번 노드의 색깔이 다를 경우

이 경우는 1번부터 $n-1$번 까지 칠하는 경우의 수가 $dp(n-1,k)$와 일대일 대응이 된다.

$n$번 칸에는 1번과 $n-1$번과 다른 색깔로 칠해야 하므로 $k-2$개의 색깔중 하나를 골라서 칠할 수 있다.

따라서 이 경우의 수는 $(k-2) \times dp(n-1,k)$이다.

case 2) 1번 노드의 색깔과 $n-1$번 노드의 색깔이 같을 경우

이 경우는 1번과 $n-1$번을 겹쳐서 cycle을 만든다고 생각하면, 1번부터 $n-1$번 까지 칠하는 경우의 수가 $dp(n-2,k)$와 일대일 대응이 된다.

$n$번 칸에는 1번과 $n-1$번과 다른 색깔로 칠해야 하는데, 두 색깔이 같으므로 $k-1$개의 색깔중 하나를 골라서 칠할 수 있다.

따라서 이 경우의 수는 $(k-1) \times dp(n-2,k)$이다.

종합해보면 $dp(n,k)=(k-2) \times dp(n-1,k) + (k-1) \times dp(n-2,k)$이다.

여기서 초기값을 잘 생각해보아야 하는데, $n \geq 2$일 때에는 $dp$값과 구하고자 하는 사이클의 색칠 값이 같지만, $n=1$일 때에는 사이클의 색칠하는 경우의 수는 $k$이지만 $dp$값은 0이어야 한다.

따라서 $dp(1,k)=0, dp(2,k)=k^2-k$로 dp테이블을 먼저 채워준 후, $dp(1,k)=k$로 정의해야 한다.

다음은 트리 부분의 경우의 수를 구해보자.

이 부분은 어렵지 않은데, 각 노드들은 유일한 부모노드가 존재하며, 위에서부터 부모의 색깔과 다르게 칠하기만 해면 재귀적으로 칠할 수 있으므로, 각 칸마다 $k-1$가지의 색깔로 칠할 수 있다.

요약하자면 주어진 input에 $t$개의 component가 있고 각각의 component를 구성하는 cycle의 크기를 $c_i$라고 하면, 총 경우의 수는 다음과 같은 식으로 표현이 가능하다.

$$\prod_{i=1}^t dp(c_i,k) \times (k-1)^{(n-\sum_{i=1}^t c_i)}$$

cycle의 탐색은 DFS탐색을 하면서 visitTime을 관리하면 쉽게 할 수 있다.

출발한 노드의 visitTime과 도착한 노드의 visitTime을 비교했을 때, 출발한 노드의 visitTime이 더 크다면, 지금 도착한 노드는 이미 계산이 끝난 노드이므로 무시하고, 도착한 노드의 visitTime이 더 크다면 현재시간과 도착한 노드의 시간의 차이가 cycle의 크기가 된다.

따라서 시간복잡도는 $dp$ 테이블을 채우는데 $O(n)$, DFS를 하면서 cycle 부분의 색칠 수를 곱하는데에 $O(n)$ 나머지 트리 부분의 색칠 수를 곱하는데에 $O(n)$(이 부분은 $O(logn)$에도 가능하지만 bottleneck이 아니므로 무시)으로, 총 시간복잡도는 $O(n)$이다.

Time Complexity : $O(n)$

코드

#include<iostream>
#include<algorithm>
#define N 1000004
#define MOD 1000000007

using namespace std;

int n,k;
int a[N],t[N];
typedef long long ll;
ll dp[N];
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];

	dp[0]=k;
	for(int i=2;i<=n;i++) dp[i] = (dp[i-1]*(k-2)+dp[i-2]*(k-1))%MOD;
	dp[1]=k;
    
	int c=1,cnt=0;
	ll ans=1;

	for(int i=1;i<=n;i++)
	{
		if(t[i]!=0)continue;
		int j=i;
		for(;t[j]==0; j=a[j]) t[j]=c++;
		if(t[j]>=t[i])
		{
			int x = c-t[j];
			ans = (ans*dp[x])%MOD;
			cnt += x;
		}
	}
	for(int i=n-cnt;i>0;i--) ans = (ans * (k-1))%MOD;
	cout<<ans;
}