import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**4)
def DFS(now):
global id,s
visited[now] = nowid = id
stack.append(now)
for next in graph[now]:
if sccnum[next]:
continue
if not visited[next]:
id += 1
DFS(next)
visited[now] = min(visited[now],visited[next])
if visited[now]==nowid:
s = len(scc); scc.append([])
while stack:
x = stack.pop()
sccnum[x] = s; scc[-1].append(x)
if x==now:
break
def check():
for i in range(1,N+1):
if sccnum[i]==sccnum[-i]:
return
return 1
def dfs(now):
visited[now] = 1; visited[-now] = 0
for next in graph[now]:
if visited[next]==-1:
dfs(next)
N,M = map(int,input().split())
graph = [[] for i in range(2*N+1)]
for _ in range(M):
q = [*map(lambda x:1 if x=="R" else -1 if x=="B" else int(x),input().split())]
for i in range(3):
for j in [1,2]:
j = (i+j)%3
graph[-q[i*2]*q[i*2+1]].append(q[j*2]*q[j*2+1])
visited = [0]*(2*N+1); scc = [[]]; sccnum = [0]*(2*N+1); stack = []
for i in range(1,N+1):
if not visited[i]:
id = 1
DFS(i)
if check():
visited = [-1]*(2*N+1); scc.reverse()
for s in scc:
for i in s:
if visited[i]==-1:
visited[i] = 0; dfs(-i)
print(*map(lambda x:"R" if x==1 else "B",visited[1:N+1]),sep="")
else:
print(-1)
2-SAT 응용문제
2-SAT 문제라는 사실을 알고 문제를 풀어서 그런지 쉽게 해결할 수 있었다.
핵심은 2~3명이 맞춰야 한다는 것이다. 원래 2-SAT 문제를 풀 때 (X V Y) 가 있으면 X가 부정일 때 Y가 무조건 참이라는 사실을 이용해서 그래프를 만들었었다. 이와같이, 이 문제에서 3개의 전등 X,Y,Z가 있다고 가정하면, X를 맞추지 못했을 경우 Y와 Z가 무조건 참이어야 한다. Y가 거짓일때도 X,Z가 무조건 참이어야 하고 Z도 마찬가지이다.
따라서 이를 그래프로 나타내줄 수 있고, 그래프로 나타내기만 하면 풀이 방식은 2-SAT - 4 [백준 11281번] 2-SAT - 4 (Python3) (tistory.com) 문제와 완전히 똑같다.
2-SAT라는 사실을 알고 풀어서 쉽게 해결했지만 만약 몰랐다면 전등이 3개라는 사실에 속아서 2-SAT라는 사실을 떠올리기 힘들었을 수도 있었겠다는 생각이 드는 문제였다.
오늘의 교훈) 다양한 2-SAT 문제를 해결하자