본문 바로가기

카테고리 없음

[백준 1420번] 학교 가지마! (Python3)

from collections import *
dy = [1,-1,0,0]; dx = [0,0,1,-1]

def BFS():
  visited = [-1]*N*M*2; visited[K+N*M] = K
  dq = deque([K+N*M])
  while dq:
    now = dq.popleft()
    if now==H:
      return visited
    for next,c in graph[now]:
      if visited[next]<0 and c-flow[now][next]:
        visited[next] = now
        dq.append(next)

def solve():
  if (H,1) in graph[K+N*M]:
    return -1
  result = 0
  while visited:=BFS():
    now = H
    result += 1
    while now!=K:
      last = visited[now]
      flow[last][now] += 1; flow[now][last] -= 1
      now = last
  return result

N,M = map(int,input().split())
board = [input() for i in range(N)]
graph = [[(N*M+i,1)] for i in range(N*M)]+[[(i,0)] for i in range(N*M)]
for y in range(N):
  for x in range(M):
    if board[y][x]=="K":
      K = y*M+x
    if board[y][x]=="H":
      H = y*M+x
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0 and board[y1][x1]!="#":
        graph[y1*M+x1+N*M].append((y*M+x,1))
        graph[y*M+x].append((y1*M+x1+N*M,0))
flow = [{i:0 for i,c in graph[n]} for n in range(N*M*2)]
print(solve())

최대유량 응용문제

이 문제는 K-H를 분리하는 문제로, 최소컷 문제로 볼 수 있다. 이때 최대유량-최소컷 정리에 따라 최소컷 = 최대유량임이 알려져있고, 따라서 최대유량 문제로 치환하여 해결할 수 있다.

 

이때 벽을 세우는데, 벽을 정점과 정점 사이에 세우는 것이 아니라 정점에 세우게 된다. 따라서 정점 그 자체를 하나의 간선으로 취급해야하며 이는 도시 왕복하기 2 https://rapun7el.tistory.com/372 문제와 유사한 문제임을 알 수 있다.

 

풀이를 설명하면,

1. 정점의 개수가 N*M개 이므로 그 2배인 크기 N*M*2의 인접그래프를 만든다.

2. y,x 좌표의 경우 i=y*M+x가 곧 자신의 번호이다. 이때 i와 i+N*M간에 용량 1의 간선을 만들고 역방향은 용량 0의 간선을 만든다. (도시왕복하기 2와 동일)

3. 벽(#)을 제외한 나머지 인접한 정점에 대해서 용량 1의 간선을 만들고 역방향은 용량 0의 간선을 만든다.

4. K와 H가 인접한 경우 -1을 출력하고, 그렇지 않은 경우 최대유량을 구하여 출력한다.

 

참고로 N*M*2가 최대 20000 이므로 graph나 flow를 n*n 인접행렬로 구성하면 메모리 초과가 발생하게 된다. 나는 그래프는 인접리스트를, flow는 dict를 이용하였다.

 

 

오늘의 교훈) 최소컷 문제는 최대유량 문제로 치환하여 해결할 수 있다.