d = [1,0,-1,0]
dd = {(1,-1,-1,1):1,(1,1,-1,-1):2,(-1,1,1,-1):3,(-1,-1,1,1):4}
def DFS(now):
global id
ID[now] = nowid = id
stack.append(now)
for next in graph[now]:
if check[next]:
continue
if not ID[next]:
id += 1
DFS(next)
ID[now] = min(ID[now],ID[next])
if ID[now]==nowid:
SCC.append([])
while 1:
x = stack.pop()
check[x] = 1; SCC[-1].append(x)
if x==now:
return
def dfs(now):
TF[now] = 1; TF[now-4+8*int(now%8<4)] = -1
for next in graph[now]:
if not TF[next]:
dfs(next)
def find(y,x,i):
while N>(y:=y+d[i])>=0 and M>(x:=x+d[i-1])>=0 and (t:=board[y][x])!="#":
if type(t)==int:
return t
N,M = map(int,input().split())
board = [[*input()] for i in range(N)]
T = 1; tower = []; clone = []
for y in range(N):
for x in range(M):
if board[y][x]=="T":
board[y][x] = T; tower.append((y,x,T))
T += 1
if board[y][x]=="n":
clone.append((y,x))
graph = [[] for i in range(T*8)]
for y,x,t in tower:
for i in range(4):
graph[t*8+i+4].append((t*8+(i-2)%4)); graph[t*8+i].append(t*8+(i-2)%4+4)
if find(y,x,i):
graph[t*8+i].append(t*8+i+4)
for y,x in clone:
f = [find(y,x,i) for i in [2,3,0,1]]
for i in range(4):
if t:=f[i]:
if not f[i-1] and not f[i-3]:
graph[t*8+i+4].append(t*8+i)
else:
for j in range(4):
if abs(i-j)%2 and f[j]:
graph[t*8+i+4].append(f[j]*8+j)
ID = [0]*T*8; stack = []; SCC = []; check = [0]*T*8
for i in range(T*8):
if not check[i]:
id = 1
DFS(i)
SCC.reverse(); TF = [0]*T*8
for scc in SCC:
for s in scc:
if not TF[s]:
dfs(s-4+8*int(s%8<4))
for y,x,t in tower:
board[y][x] = dd[tuple(TF[t*8:t*8+4])]
for b in board:
print(*b,sep="")2-sat 응용문제
L퍼즐 [백준 3654번] L퍼즐 (Python) (tistory.com) 풀이와 거의 유사하다.
풀이를 설명하면,
1. 타워의 위치와 클론의 위치를 찾아 저장하고, 타워에는 순서대로 번호를 부여한다.
2. 각 타워의 4방향을 노드로 두고, 참일 경우 해당 방향으로 발사함을 의미한다.
3. 각 타워의 4방향에 대해 어떤 방향과 반대방향이 동시에 참일 수 없으며 동시에 거짓일 수 없다. (L퍼즐과 유사)
4. 각 타워의 4방향 중, 벽이나 범위 밖까지 끝까지 확인했을 때 다른 타워를 만나는 경우 해당 방향은 참일 수 없다.
5. 각 클론에서 4방향으로 확인했을 때, 만나는 타워가 1개면 그 타워는 클론방향으로 반드시 참이어야하고, 2개 이상이라면 어떤 타워가 거짓이면 다른 타워는 참이어야한다.
6. 3~5의 명제를 토대로 2-sat + 역추적 [백준 11281번] 2-SAT - 4 (Python3) (tistory.com) 을 이용하여 해를 구하고 출력한다.
L퍼즐을 풀고 나서 푸니 한결 더 수월했지만 그래프를 만드는데 필요한 구현량이 많고, 그에 따른 실수도 많이 나온 문제였다.
여담) 내 풀이가 숏코딩 순위 1위와 파이썬 기준 성능 1위가 되었다.
