import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
d = [1,0,-1,0]
def DFS(now):
global id,S
ID[now] = nowid = id
stack.append(now)
for next in graph[now]:
if scc[next]:
continue
if not ID[next]:
id += 1
DFS(next)
ID[now] = min(ID[now],ID[next])
if ID[now]==nowid:
S += 1
while 1:
x = stack.pop()
scc[x] = S
if x==now:
return
def check():
if sum(board[i].count("W") for i in range(N))!=B*2:
return 1
for b in range(B):
for i in range(4):
if scc[b*8+i]==scc[b*8+i+4]:
return 1
for _ in range(int(input())):
N,M = map(int,input().split())
board = [[*input().strip()] for i in range(N)]
B = 0; black = []
for y in range(N):
for x in range(M):
if board[y][x]=="B":
board[y][x] = B; black.append((y,x,B))
B += 1
graph = [[] for i in range(B*8)]
for y,x,b in black:
for i in range(4):
graph[b*8+i+4].append(b*8+(i-2)%4); graph[b*8+i].append(b*8+(i-2)%4+4)
if N>(y1:=y+d[i])>=0 and M>(x1:=x+d[i-1])>=0 and board[y1][x1]=="W":
for j in range(4):
if i==(j-2)%4:
continue
if N>(y2:=y1+d[j])>=0 and M>(x2:=x1+d[j-1])>=0 and type(b2:=board[y2][x2])==int:
graph[b*8+i].append(b2*8+(j-2)%4+4)
else:
graph[b*8+i].append(b*8+i+4)
ID = [0]*B*8; stack = []; scc = [0]*B*8; S = 0
for i in range(B*8):
if not scc[i]:
id = 1
DFS(i)
print("NO" if check() else "YES")
2-sat 응용문제
검은색 조각을 기준으로 인접한 조각과 연결 할 수 있는지를 이용해 2-sat로 치환할 수 있다.
풀이를 설명하면,
1. 검은색 조각을 찾고, 각 조각에 1~B까지 번호를 부여한다.
2. 각 검은색 조각을 기준으로 4방향을 노드로 두고, 참일 경우 현재 검은색 조각이 해당 방향과 연결되어 있음을 의미한다.
3. 각 검은색 조각을 기준으로 상하좌우 4방향에 대해 어떤 방향과 반대방향이 동시에 참일 수 없으며 동시에 거짓일 수 없다. (동시에 참이면 L자가 될 수 없고, 동시에 거짓이면 퍼즐이 만들어지지 않는다)
4. 각 검은색 조각을 기준으로 4방향 중 어떤 방향이 흰 조각이 아니거나, 범위 밖인 경우에는 참일 수 없다.
5. 어떤 흰색 조각을 기준으로 여러개의 검은색 조각이 인접해 있는 경우, 인접한 각 검은색 조각의 흰색 조각으로의 방향들은 한개가 참이면 나머지는 거짓이 된다. (각 흰색 조각은 한 개의 검은색 조각과 연결되므로)
6. 3~5의 명제를 이용해서 그래프를 만들어 2-sat로 치환하고, 타잔알고리즘으로 결과를 낸다.
7. 만약 흰색 조각의 개수가 검은색 조각의 개수의 2배이고, 2-sat가 성립하는 경우 YES를 출력한다.
2-sat 문제라는 것을 알면 크게 어렵지 않은 문제이지만, 모른 채로 풀었다면 2-sat라는 것을 발견할 수 있었을까 하는 의문이 들 정도로 잘 숨겨진 문제였다. 또, 그래프를 만드는데 여러가지 실수가 발생하기 쉽고, 마지막에 7번으로 개수를 점검하는것까지 해서 꽤나 까다로운 문제였다.