본문 바로가기

카테고리 없음

[백준 7577번] 탐사 (Python)

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인 경우에는 거리를 음수로 두고 최단거리를 갱신하는 방식으로 해결한 것 같다. 해당 풀이도 참고해보아야겠다.