[Python] 1420 - 학교 가지마! (플래티넘2)

1. 문제 설명

https://www.acmicpc.net/problem/1420

1420번: 학교 가지마!

알고리즘 책 펴놓고 몇 시간을 연구해서 겨우 풀었었다. ㅋㅋ..

블로그에 올린 코드는 문제를 풀고난 이후에 다른 사람들이 올린 설명을 보면서 다듬었다.

 

[백준] No.1420 - 학교 가지마! (C++, 최소 컷, 최대 유량, 정점 분할)

설명을 엄청 잘 해놓으셔서 많은 도움이 되었었다.

이번 포스팅은 이 블로그에서 설명해주신 내용을 이해하는 과정을 정리해놓은 것으로 보면 된다.

 

---

2. 아이디어

문제 자체는 최소 컷, 최대 유량 알고리즘이긴 한데, 내용이 조금 복잡해진다.

이게 왜 최대 유량 문제로 접근 가능하냐고 한다면 각 정점을 이동하는 비용을 무한대로 잡고

1씩 흘렸을 때에 source에서 sink까지 도달하는 횟수가 곧 경로의 개수를 의미하므로 그만큼 벽을 세우면 된다.

 

결론부터 써놓으면 이 문제는 정점 분할을 해주어야 하는데,

포스팅 하다가 보니 대체 정점 분할을 왜 해줬어야 하는지 도통 생각이 안 난다. ㅋㅋㅋㅋ....

그 때는 이해하고 넘어갔던 거 같은데, 굳이 왜 분할해야 하지? 라는 생각이 머릿속에서 안 떠나길래

혼자 다시 생각해보니까 visited라는 방문 여부를 묻는 리스트를 따로 만들지 않기 위함인 거 같기도 하고

그냥 모든 flow를 1로 정하고 visited를 사용해서 구현해도 될 거 같기도 한데

그러면 100x100 크기의 맵에서 시간 초과가 날 수도 있기 때문이 아닐까?? 나중에 구현해봐야겠다.

 

정점 분할

이전 최대 유량 문제에서는 방문 여부를 확인하는 visited 리스트를 하나 만들고,

유량을 흘려가는 방식을 사용했었는데 이번에는 정점을 두 개로 분할하여 각 정점 간에는 INF만큼의

용량을 설정하고, 정점 내부에서는 in-1-out 만큼의 용량을 설정한다.

이때 in-1-out안에 1만큼 flow가 생긴다면 해당 정점을 이미 방문했다는 것과 같은 의미를 지닌다.

Network Flow의 기본 원칙에 따라서 역방향 간선을 추가해주기 위해

이전 정점의 in 노드와 현재 정점의 out 노드를 연결해준다.

 

이렇게 풀이했을 때, 테스트 케이스 중 하나를 살펴보자.

 

하나의 흐름이 발생했으므로 사이에 in-out의 연결을 끊어주는 횟수가 곧 벽을 세우는 횟수가 된다.

사실 말이 좋아서 연결을 끊어준다는 표현을 사용하지, 그냥 flow가 발생할 수 있는 경로를 체크하는 것

하나의 예시를 더 살펴보자.

 

처음 언급한 블로그에서 들었던 예시를 그대로 인용했다.

실제로 해당 값을 넣고 디버깅 해보니까 정말 저런 흐름으로 흘러가는 것을 확인할 수 있었다.

마찬가지로 정점분할을 해서 디테일하게 그려보면

 

유령 간선을 통해 상쇄가 일어나고 두 개의 flow가 생기므로 벽을 2개 세우면 정답이 된다.

댕어렵다...

 

---

3. 코드

import sys
from collections import deque

input = sys.stdin.readline
INF = int(1e9)

def updateEdge(u, v, x): # u, v 정점, x 유량
    adj[u].append(v)
    adj[v].append(u)
    cost[u][v], cost[v][u] = x, 0
    flow[u][v], flow[v][u] = 0, 0

def dfs():
    result = 0

    while True:
        parent = [-1]*(size)
        queue = deque()
        queue.append(source)

        while queue:
            pre = queue.popleft()
            for now in adj[pre]:
                if parent[now] == -1 and cost[pre][now] - flow[pre][now] > 0:
                    queue.append(now)
                    parent[now] = pre

        if parent[sink] == -1: break

        idx = sink
        while idx != source:
            flow[parent[idx]][idx] += 1
            flow[idx][parent[idx]] -= 1
            idx = parent[idx]
        result += 1
    return result

def solution():
    if (n == 1 and m == 1) or abs(sy - ty) + abs(sx - tx) == 1: # exeption handling
        print(-1) # K와 H가 맞닿아 있는 경우 제거
        return

    for i in range(n*m): # 정점 in, out 분리 후 서로 연결
        updateEdge(2*i, 2*i+1, 1)

    current = 0
    for row in range(n): # 인접 인덱스에 장애물이 없다면 유량 MAX
        for col in range(m):
            if row + 1 < n and graph[row][col] != '#' and graph[row+1][col] != '#':
                _next = current + 2 * m
                updateEdge(current+1, _next, INF)
                updateEdge(_next+1, current, INF)
            if col + 1 < m and graph[row][col] != '#' and graph[row][col+1] != '#':
                _next = current + 2
                updateEdge(current+1, _next, INF)
                updateEdge(_next+1, current, INF)
            current += 2
    return print(dfs())
    
if __name__ == "__main__":
    n, m = map(int, input().split())
    size = 2*n*m
    graph = [[] for _ in range(n)]   # 원본
    adj = [[] for _ in range(size)]  # 정점 연결 정보
    cost = [{} for _ in range(size)] # 각 간선의 최대 유량
    flow = [{} for _ in range(size)] # 실제로 흐르는 유량
    cnt = 0

    for row in range(n):
        graph[row] += list(input().rstrip())
        for col in range(m):
            if graph[row][col] == 'K':
                sy, sx = row, col
                source = cnt + 1
            elif graph[row][col] == 'H':
                ty, tx = row, col
                sink = cnt
            cnt += 2

    solution()