import sys,collections
input = lambda: [*map(int,sys.stdin.readline().split())]
def SPFA():
inq = [[0]*(K+1) for i in range(K+1)]
while dq:
a,b = dq.popleft()
inq[a][b] = 0; q = []
if upper[a][b]<0:
return 1
for i in range(a):
if upper[i][a]>(s:=upper[i][b]-lower[a][b]):
upper[i][a] = s
q.append((i,a))
if lower[i][a]<(s:=lower[i][b]-upper[a][b]):
lower[i][a] = s
q.append((i,a))
if upper[i][b]>(s:=upper[i][a]+upper[a][b]):
upper[i][b] = s
q.append((i,b))
if lower[i][b]<(s:=lower[i][a]+lower[a][b]):
lower[i][b] = s
q.append((i,b))
for i in range(a,b):
if upper[a][i]>(s:=upper[a][b]-lower[i][b]):
upper[a][i] = s
q.append((a,i))
if lower[a][i]<(s:=lower[a][b]-upper[i][b]):
lower[a][i] = s
q.append((a,i))
if upper[i][b]>(s:=upper[a][b]-lower[a][i]):
upper[i][b] = s
q.append((i,b))
if lower[i][b]<(s:=lower[a][b]-upper[a][i]):
lower[i][b] = s
q.append((i,b))
for i in range(b,K+1):
if upper[a][i]>(s:=upper[a][b]+upper[b][i]):
upper[a][i] = s
q.append((a,i))
if lower[a][i]<(s:=lower[a][b]+lower[b][i]):
lower[a][i] = s
q.append((a,i))
if upper[b][i]>(s:=upper[a][i]-lower[a][b]):
upper[b][i] = s
q.append((b,i))
if lower[b][i]<(s:=lower[a][i]-upper[a][b]):
lower[b][i] = s
q.append((b,i))
for a,b in q:
if not inq[a][b]:
inq[a][b] = 1; dq.append((a,b))
def solve():
for a,b,c in data:
if c>b-a+1:
return "NONE"
lower[a-1][b] = upper[a-1][b] = c
dq.append((a-1,b))
while dq:
if SPFA():
return "NONE"
for i in range(K):
if lower[i][i+1]!=upper[i][i+1]:
lower[i][i+1] = 1
dq.append((i,i+1))
break
return ["#" if lower[i][i+1] else "-" for i in range(K)]
K,N = input()
data = [input() for i in range(N)]
lower = [[0]*(K+1) for i in range(K+1)]
upper = [[j-i for j in range(K+1)] for i in range(K+1)]
dq = collections.deque()
print(*solve(),sep="")SPFA를 변형하여 해결하였다.
풀이를 설명하면,
1. lower bound 그래프와 upper bound 그래프를 설정한다. lower[a][b]는 a~b 사이에 존재해야하는 최소한의 물체의 개수를, upper[a][b]는 최대 개수를 의미한다.
2. upper의 초깃값은 b-a의 차이이고 (모든 칸이 차있을 경우), lower의 초깃값은 0이다.
3. data의 값은 정확한 값이므로 a,b,r이 주어질 때, lower[a][b]와 upper[a][b]를 모두 갱신해주고 deque에 (a,b)를 넣는다.
4. deque에 (a,b)를 삽입하면 inq를 갱신하고, (a,b)가 pop되면 a-b 사이에 변화가 일어났다는 뜻이므로 최대최소 관계에 따라 i = 1~K+1에서 변화가 일어나는지 관찰하고 변화가 일어나면 inq에 없을 경우 deque에 삽입한다. (SPFA와 유사)
5. 4를 전부 돌렸을 때, lower[i][i+1]과 upper[i][i+1]이 다를 경우 upper[i][i+1]을 1로 바꾸고 SPFA를 돌린다. (변화가 없을때까지 계속 반복)
6. 4를 돌리는 과정에서 upper가 음수가 되면 무한사이클이 생기므로 NONE을 출력한다. 또, 입력된 데이터의 숫자가 불가능할 경우 (즉 a~b 사이에 b-a보다 더 큰 수가 들어갈 경우) NONE을 출력한다.
7. 6이 아닌 경우 lower[i][i+1]을 1인지 0인지에 따라 # 또는 -로 출력한다.
즉, a-b 사이에 변화가 일어날 경우에 변화와 관련된 모든 구간을 갱신해주고, 또 그 변화로 인해 변화가 일어난 구간을 갱신해주면서, 만약 모든 갱신이 끝나도 결과가 특정되지 않을 경우 하나씩 1로 고정한 뒤 다시 갱신하는 방식이다.
풀이가 굉장히 길어졌는데, 길어진 이유는 갱신하는 과정에서 a,b의 대소에 따른 변화를 깔끔하게 나타내지 못하고 모든 분기를 나누어주었기 때문이다. 다른 사람들의 풀이를 보니 플로이드 워셜이나 SPFA (변형하지 않은) 를 이용한 경우가 많았다. 어떻게 해결한 것인가 하니 a>b인 경우에는 거리를 음수로 두고 최단거리를 갱신하는 방식으로 해결한 것 같다. 해당 풀이도 참고해보아야겠다.