[백준 3654번] L퍼즐 (Python)

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번으로 개수를 점검하는것까지 해서 꽤나 까다로운 문제였다.