BOJ(백준) 3654번 L퍼즐

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

풀이의 발상 자체는 2-sat 문제인 것을 떠올리면 그렇게 복잡하지 않다. 하지만 기본적인 2-sat 문제의 티어가 플래티넘 4임에도 이 문제가 다이아 4인 것은 구현이 상당히 귀찮기 때문이다.

강한 연결 요소(SCC)를 통한 2-sat 문제의 해결 방법에 대해 안다고 생각하고 풀이를 써보겠다.

하나의 검은색 칸의 오른쪽, 왼쪽과 아래쪽, 위쪽을 각각 한 쌍의 true와 false라고 기준으로 잡고 문제에 접근해보자. 검은색 칸의 오른쪽과 왼쪽 중 하나에는 흰색이 붙어 있어야 된다. 여기서 오른쪽을 true, 왼쪽을 false라고 하자.

만약 오른쪽이 흰색칸이 아니라면 true이면 안 된다. 이 표현은 p → ¬p로 가능하다(true이면 즉시 모순이 되게함). 마찬가지로 왼쪽이 흰색칸이 아니라면 false이면 안 된다.

이제 이 방식을 똑같이 검은색 칸의 위쪽과 아래쪽 쌍에도 적용시키면 된다.

여기까지면 구현하는 것이 그렇게 복잡하지는 않겠지만 해결해야될 문제가 하나 더 있다. 바로 두 개의 검은 칸이 하나의 흰색 칸을 같이 차지하면 안 된다는 것이다.

그래서 다시 각각의 흰색칸이 한 방향에 있는 검은색에 의해 차지되면 다른 방향에 있는 검은색들은 차지를 못하도록 해야한다. 이 부분은 각각의 흰색 칸에 대해서 이중 반복문으로 처리가 가능하다.

AC code

#include <bits/stdc++.h>

using namespace std;
int N,M,ord,cnt,t1,t2,c1,c2,c3,T,board[500][500],r,c,wnum,bnum;
int dy[]={1,-1,0,0},dx[]={0,0,1,-1},mul1[]={0,0,1,1},mul2[]={1,0,1,0},mul3[]={0,1,0,1};
char tmp;
vector<vector<int>>sccs,grp;
vector<int>sccnum,vis,sol;
stack<int> s;

int notCal(int n)
{
	if(n<=N) return n+N;
	else return n-N;
}

int tarjan(int loc)
{
	int minord=vis[loc]=++ord;
	s.push(loc);
	for(int i:grp[loc]) {	
		if(!vis[i])minord=min(tarjan(i),minord);
		else if(!sccnum[i])minord=min(vis[i],minord);
	}
	if(minord==vis[loc]) {
		cnt++;
		vector<int> v;
		while(1)
		{
			t1=s.top();
			s.pop();
			v.push_back(t1);
			sccnum[t1]=cnt;
			if(loc==t1) break;
		}
		sccs.push_back(v);
	}
	return minord;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--)
	{
		wnum=bnum=0;
		cin>>r>>c;
		for(int i=0;i<r;i++) for(int k=0;k<c;k++) {
			cin>>tmp;
			if(tmp=='B') {
				bnum++;
				board[i][k]=bnum;
			}
			else if(tmp=='W') {
				wnum++;
				board[i][k]=-1;
			}
			else board[i][k]=0;
		}
		N=bnum*2;
		sccs=vector<vector<int>>(1),
		grp=vector<vector<int>>(2*N+1);
		sccnum=vis=sol=vector<int>(2*N+1);
		ord=cnt=c3=0;
		
		//이 반복문이 핵심 
		for(int a=0;a<r;a++) for(int b=0;b<c;b++) {
			if(board[a][b]>0) {
				int cy=a,cx=b;
				for(int k=0;k<4;k++) {
					int ny=cy+dy[k],nx=cx+dx[k];
					if(ny<0||ny>=r||nx<0||nx>=c||board[ny][nx]!=-1) grp[board[a][b]+(N/2)*mul1[k]+N*mul3[k]].push_back(notCal(board[a][b]+(N/2)*mul1[k]+N*mul3[k]));
				}
			} else if(board[a][b]==-1) {
				int cy=a,cx=b;	
				for(int k=0;k<4;k++) {
					int ny=cy+dy[k],nx=cx+dx[k];
					if(ny<0||ny>=r||nx<0||nx>=c||board[ny][nx]<1) continue;
					for(int j=0;j<4;j++) {
						int nny=cy+dy[j],nnx=cx+dx[j];
						if(nny==ny&&nnx==nx) continue;
						if(nny<0||nny>=r||nnx<0||nnx>=c||board[nny][nnx]<1) continue;
						grp[board[ny][nx]+(N/2)*mul1[k]+N*mul2[k]].push_back(board[nny][nnx]+(N/2)*mul1[j]+N*mul3[j]);
					}
				}
			}
		}
		
		for(int i=1;i<=2*N;i++)if(!vis[i])tarjan(i);
		vector<int>ind(cnt+1);
		for(int i=1;i<=2*N;i++)for(int k:grp[i]) {
			if(sccnum[i]==sccnum[k])continue;
			ind[sccnum[k]]++;
		}
		queue<int> q;
		for(int i=1;i<=cnt;i++)if(!ind[i])q.push(i);
		while(!q.empty())
		{
			t1=q.front();
			q.pop();
			c1=c2=0;
			for(int i:sccs[t1]) {
				if(sol[i]==1)c1=1;
				else if(sol[i]==-1)c2=1;
				for(int k:grp[i]) {
					ind[sccnum[k]]--;
					if(!ind[sccnum[k]])q.push(sccnum[k]);
				}
			}
			if(c1&&c2) {
				c3=1;
				break;
			}
			if(!c1)c1=-1;
			for(int i:sccs[t1]) {
				sol[i]=c1;
				if(sol[i]==sol[notCal(i)]) {
					c3=1;
					break;
				}
				sol[notCal(i)]=c1*-1;
			}
			if(c3)break;
		}
		if(!c3&&wnum==bnum*2)cout<<"YES\n";
		else cout<<"NO\n";
	}
}