[백준 2316번] 도시 왕복하기 2 (Python3)

import sys
from collections import *
def input(): return map(int,sys.stdin.readline().split())

def BFS():
  visited = [-1]*N
  dq = deque([(1,0)])
  while dq:
    now,last = dq.popleft()
    if visited[now]<0:
      visited[now] = last
      if now==2:
        return visited
      for next in graph[now]:
        if graph[now][next]-flow[now][next]:
          dq.append((next,now))

def solve():
  while visited:=BFS():
    now = 2
    while now:
      last = visited[now]
      flow[last][now] += 1; flow[now][last] -= 1
      now = last

N,M = input(); N *= 2
graph = [{} for i in range(N)]
for i in range(N//2):
  graph[i*2][i*2+1] = 1; graph[i*2+1][i*2] = 0
for _ in range(M):
  a,b = input()
  graph[a*2-1][b*2-2] = graph[b*2-1][a*2-2] = 1
  graph[a*2-2][b*2-1] = graph[b*2-2][a*2-1] = 0
flow = [[0]*N for i in range(N)]
solve()
print(sum(flow[i][2] for i in range(N)))

최대유량 문제이자, 도시 왕복하기 [백준 17412번] 도시 왕복하기 1 (Python3) (tistory.com) 문제의 업그레이드 버전

같은 간선을 중복하면 안되는 도시 왕복하기에서, 같은 정점도 중복하지 않는 조건이 추가되었다.

 

어떻게 해결할까 고민하다가, 정점을 두 개로 분리하는 아이디어를 생각해냈다.

 

즉 아이디어를 설명하면(도시 왕복하기 1을 풀었다는 가정하에),

1. N을 2배로 늘려준다. 그리고 i*2, i*2+1 인덱스가 i번 정점을 의미한다.

2. i*2 - i*2+1 사이에 간선을 만들어준다. 다시말해 자기 자신을 한번 더 거치는 간선을 의미한다.

3. 서로 다른 도시의 경우에, i 정점과 j 정점 사이에 간선이 존재하면, i*2+1 - j*2 사이에 간선이 존재하고, j*2+1 - i*2 사이에 간선이 존재한다. (양방향이기 때문)

 

위와같이 그래프를 만들어주면 자기 자신을 거치는 간선의 용량이 1이기 때문에 모든 정점은 1번밖에 지날 수 없게 된다. 그러면 나머지는 도시 왕복하기 1과 똑같은 방식으로 해결할 수 있다.

 

간선을 분할해준다는 점에서 길의 개수 [백준 1533번] 길의 개수 (Python3) (tistory.com) 문제와 아이디어가 비슷했던 것 같다. 재미있는 문제였다.

 

 

오늘의 교훈) 다양한 최대유량 문제를 해결하자