본문 바로가기

카테고리 없음

[백준 1210번] 마피아 (Python3)

import sys
input = sys.stdin.readline
from collections import *

def BFS():
  dq = deque([0])
  level = [0]*K; level[0] = 1
  lvadj = [[] for i in range(K)]
  while dq:
    now = dq.popleft()
    for next in adj[now]:
      if graph[now][next]:
        if not level[next]:
          level[next] = level[now]+1
          dq.append(next)
        if level[next]==level[now]+1:
          lvadj[now].append(next)
  if level[K-1]:
    return lvadj

def DFS(now,f):
  if now==K-1:
    return f
  while lvadj[now]:
    next = lvadj[now].pop()
    f1 = DFS(next,min(f,graph[now][next]))
    if f1:
      graph[now][next] -= f1; graph[next][now] += f1
      lvadj[now].append(next)
      return f1

def solve():
  dq = deque([0])
  visited = [0]*K
  while dq:
    now = dq.popleft()
    for next in adj[now]:
      if graph[now][next] and not visited[next]:
        visited[next] = 1
        dq.append(next)
  for i in range(1,N+1):
    if visited[i] and not visited[i+N]:
      print(i,end=" ")

N,M = map(int,input().split()); K = N*2+2
graph = [[0]*K for i in range(K)]; adj = [[] for i in range(K)]
s,e = map(int,input().split())
graph[0][s] = graph[e+N][K-1] = 1e12
adj[0].append(s); adj[s].append(0)
adj[e+N].append(K-1); adj[K-1].append(e+N)
for i in range(1,N+1):
  graph[i][i+N] = int(input())
  adj[i].append(i+N); adj[i+N].append(i)
for _ in range(M):
  a,b = map(int,input().split())
  graph[a+N][b] = graph[b+N][a] = 1e12
  adj[a+N].append(b); adj[b].append(a+N)
  adj[b+N].append(a); adj[a].append(b+N)
while lvadj:=BFS():
  while DFS(0,1e12):
    pass
solve()

MFMC + 디닉 알고리즘 응용문제

최대유량 최소컷 정리 문제인데 간선의 개수가 최대 20000개이기 때문에 에드몬드-카프를 사용할 수 없다. 따라서 디닉 알고리즘을 공부해서 해결하였다.

 

풀이를 설명하면,

1. 각 톨게이트를 i번의 경우 i번과 i+N번으로 분할한다.

2. i-i+N 사이에 톨게이트 비용을 용량으로 갖는 간선을 만든다.

3. source-시작지점, 도착지점-sink, 그리고 고속도로로 이어진 톨게이트끼리 용량 무한대의 간선을 만든다.

4. 디닉 알고리즘으로 최대유량을 구한다.

5. BFS로 시작지점부터 탐색하여, i에는 도착할 수 있는데 i+N에는 도착하지 못하는 톨게이트가 곧 점거해야하는 도시이다.

 

1~4까지는 쉽게 해결할 수 있었는데, 5번을 출력하는 과정에서 애를 먹었던 문제였다. 처음에는 간선의 용량이 0이 된 도시를 출력해야한다고 생각했는데, 그렇게 되면 중복하여 출력이 발생한다는 것을 알게되었다. 그래서 꼭 필요한 간선을 찾아서 출력해야 했는데, 이 방법을 떠올리기 쉽지 않았다.

 

 

오늘의 교훈) 최대유량이 성립할 때를 추적하는 방법을 고민하자