백준 1420번: 학교 가지마! (Max Flow Min Cut)

문제링크: 1420번: 학교 가지마! (acmicpc.net)

1420번: 학교 가지마!

이 문제는 NxM 크기의 도시에 도현이의 위치와 학교의 위치와 벽의 위치가 주어졌을 때, 도현이가 학교에 갈 수 없게 하려면 최대 몇개의 벽을 세워야 하는지 구하는 문제이다. 최대 개수와 최소 개수를 생각해 보면 최소 개수는 도현이와 학교가 이미 분리된 위치에 있을 때 0, 따로 있을때 학교를 상하좌우로 막은 경우 4 이렇게 최소 0, 최대 4를 가질 수 있다.

 

이 문제를 풀기 위해서는 최대 유량 최소 컷 정리에 대해 알아야 한다. 최대 유량 최소 컷 정리란 source에서 sink까지 그래프가 연결되어 있을 때, source와 sink가 이어지지 않도록 간선을 자르는 경우 중, 최소 간선 비용을 얻을 수 있게 자르는 경우는 source에서 sink까지의 최대 유량을 구하면 된다는 것이다.

 

처음에 이 문제를 풀 때 N * M개의 위치를 노드로 하고 각각 상하좌우 갈 수 있는 경우를 간선으로 하고 풀었는데, 이렇게 풀면 간선을 자르는 경우와 벽을 세우는 경우가 다르기에 틀렸습니다를 받게 된다. 예시로 가독성을 위해 문제의 입력을 소문자, (.)을 o로 바꾸면:

ko#

ooo

#oh

의 경우에서 가운데 빨간색 위치에 벽을 1개만 설치해도 막히게 되지만, 상하좌우 간선으로 생각하면 가운데 위치에서 갈 수 있는 아래로 가는 간선, 오른쪽으로 가는 간선 2개를 막아야 막히게 된다.

 

이런 반례를 막기 위해 각 위치의 노드를 node_in과 node_out으로 분할하여 node_in - node_out 으로 가는 용량이 1인 간선을 할당하여 벽 설치를 구현한다. node_in -> node_out의 간선 1개를 막으면, 해당 node에서 갈 수 있는 상하좌우 간선또한 막히게 되어 해당 node를 쓰지 못하는 (벽을 세우는) 경우를 구현할 수 있다. 물론 상하좌우 이동 간선은 a->b로 이동한다 치면 (a)node_out -> (b)node_in 방향으로 구현해야 하고, 이동 간선의 용량은 1을 부여해도 되지만 이동하는 데에는 몇번이고 이동할 수 있다는 의미에서 inf를 부여하였다.

 

먼저 N,M이 각각 최대 100이므로 100 * 100 총 10000개, 분할하면 20000 의 노드가 있는데, 그래프의 간선들을 인접행렬로 구현하면 리스트의 원소 개수가 4억개가 되므로 메모리 초과가 난다.

 

내가 생각한 방법은 각 노드에 6개 원소의 리스트를 할당한다. 이 6개의 숫자는 각 노드에서의 이동 방법을 뜻한다.

 

0은 node_in -> node_out 의 노드 내부의 이동 간선,

5는 node_out -> node_in 노드 내부의 이동 간선,

1, 2, 3, 4는 각각 상하좌우 다른 노드로 이동하는 노드 외부의 간선으로 표현 해 구현하였다.

위치 (i,j) 의 node_in은 [i][j] 에 보관하고, node_out은 [i+N][j+M] 에 보관하여 구현하였다.

import sys
from collections import deque

N,M = map(int,sys.stdin.readline().rstrip().split())

#노드의 간선 표현
#0: node_in -> node_out 1:상 2:하 3:좌 4:우 5: node_out -> node_in

cap = [[[0 for _ in range(6)] for _ in range(2*M)] for _ in range(2*N)]
flow = [[[0 for _ in range(6)] for _ in range(2*M)] for _ in range(2*N)]
graph = [[[] for _ in range(2*M)] for _ in range(2*N)]
board = []
inf = 9999999

for i in range(N):
    board.append(list(sys.stdin.readline().rstrip()))

source = (-1,-1)
sink = (-1,-1)

for i in range(N): # 노드 (i,j) -> node_in: [i][j], node_out: [i+N][j+M]
    for j in range(M):
        cap[i][j][0] = 1 #node_in -> node_out cap 1할당
        graph[i][j].append(0) #0: node_in -> node_out
        graph[i+N][j+M].append(5) #5: node_out -> node_in
        
        if board[i][j] == 'K':
            source = (i,j)
        elif board[i][j] == 'H':
            sink = (i,j)
        elif board[i][j] == '#':
            continue
        
        dx = [0,0,0,-1,1]
        dy = [0,-1,1,0,0]
        
        for k in range(1,5): #1:상 2:하 3:좌 4:우 탐색 
            if 0<= i + dy[k] < N and 0<= j + dx[k] < M:
                if board[i+dy[k]][j+dx[k]] == '#':
                    continue
                cap[i+N][j+M][k] = inf #상하좌우 순방향 node_out의 cap, graph 에 할당
                graph[i+N][j+M].append(k)

                #상하좌우의 역방향은 도착 node_in의 graph에 추가
                
                if k == 1:
                    graph[i-1][j].append(2)
                elif k == 2:
                    graph[i+1][j].append(1)
                elif k == 3:
                    graph[i][j-1].append(4)
                elif k == 4:
                    graph[i][j+1].append(3)
                
ans = 0

if abs(source[0] - sink[0]) + abs(source[1] - sink[1]) == 1: #no ans 판별
    print('-1')
    sys.exit()

sourceout = (source[0] + N, source[1] + M) #source의 node_out

while 1: #DFS로 최대유량
    que = []
    que.append(sourceout)
    parent = [[-1 for _ in range(2*M)] for _ in range(2*N)]
    parent[sourceout[0]][sourceout[1]] = sourceout
    
    while que:
        r, c = que.pop()

        if 0<= r < N and 0<= c < M: #(r,c) node-in
            
            end = [(r+N, c+M), (r+N-1, c+M), (r+N+1, c+M),
                   (r+N, c+M-1), (r+N, c+M+1)] #node-in의 end 경우
            
            for k in graph[r][c]:
                if cap[r][c][k] - flow[r][c][k] > 0 and parent[end[k][0]][end[k][1]] == -1:
                    que.append(end[k])
                    parent[end[k][0]][end[k][1]] = (r,c)
                    
        else: #(r,c) node-out
            
            end = [(inf, inf), (r-N-1, c-M), (r-N+1, c-M),
                   (r-N, c-M-1), (r-N, c-M+1),(r-N, c-M)] #node_out의 end 경우, (inf, inf): for debug
            
            for k in graph[r][c]:
                if cap[r][c][k] - flow[r][c][k] > 0 and parent[end[k][0]][end[k][1]] == -1:
                    que.append(end[k])
                    parent[end[k][0]][end[k][1]] = (r,c)

    if parent[sink[0]][sink[1]] == -1:
        break

    rfrom = sink
    while rfrom != sourceout:
        rto = parent[rfrom[0]][rfrom[1]]
        
        #rto_move로 rto에서 갈 수 있는 모든 경우 rfrom과 비교하며 rto의 실제 move 확인
        #move, rmove 6으로 세팅해서 디버깅
        
        if 0<= rto[0] < N and 0<= rto[1] < M: #rto = node-in
            
            rto_move = [(rto[0]+N, rto[1]+M), (rto[0]+N-1,rto[1]+M),
                        (rto[0]+N+1,rto[1]+M),(rto[0]+N,rto[1]+M-1),(rto[0]+N,rto[1]+M+1)]
            
            move = 6 
            rmove = 6
            
            for k in range(5):
                if rto_move[k] == rfrom:
                    move = k
                    
        else: #rto = node-out
            
            rto_move = [(-1, -1), (rto[0]-N-1,rto[1]-M), (rto[0]-N+1,rto[1]-M),
                        (rto[0]-N,rto[1]-M-1),(rto[0]-N,rto[1]-M+1), (rto[0]-N, rto[1]-M)]
            move = 6
            rmove = 6
            
            for k in range(1,6):
                if rto_move[k] == rfrom:
                    move = k

        #실제 move 얻은 뒤 반대 방향 rmove
                    
        if move == 0: 
            rmove = 5
        if move == 1:
            rmove = 2
        elif move == 2:
            rmove = 1
        elif move == 3:
            rmove = 4
        elif move == 4:
            rmove = 3
        elif move == 5:
            rmove = 0
        
        flow[rto[0]][rto[1]][move] += 1
        flow[rfrom[0]][rfrom[1]][rmove] -= 1
        rfrom = rto

    ans += 1

print(ans)

여기서 최대 유량 DFS 탐색 과정에서 기존에는 graph에 단순히 도착 노드를 넣어서 바로바로 도착 (end) 노드가 어딘지 쉽게 얻을 수 있었지만, 내가 생각한 방법은 graph, cap, flow 에 아까처럼 6개의 이동방법을 저장헀기 때문에 6개의 이동 방법에 따라 도착 (end) 노드의 경우를 모두 계산하여 이동 방법 k가 주어지면 도착 노드를 얻을 수 있게 만들었다.

 

parent[i][j] 에는 각각 (i,j) 노드의 부모 노드를 튜플로 저장하였다. 노드의 방문과 이후 source - sink 최소 스패닝 트리 경로 구현에 사용될 것이다.

 

최소 스패닝 트리를 탐색하는 과정을 마치고 경로의 노드를 모두 찾아야 한다. 기존에는 parent 리스트를 통해 rfrom, rto 만 구하면 인접 리스트를 통해 해당 간선을 찾을 수 있지만, 내가 사용한 방법은 0~5 중 하나인 이동 방법 또한 알아야 한다.

 

그래서 sink에서 다시 source로 돌아가는 과정에서 번거롭지만 rto를 구하고, rto에서 이동할 수 있는 6개의 이동 방법 (rto_move) 를 모두 계산하고 rto_move를 rfrom과 비교하며 rto에서 실제로 행한 이동 방법 move를 얻어낸다, move를 얻어내면 역방향의 간선에도 flow 처리 해주어야 하므로 각 move에 따른 rmove도 얻어내고, flow 리스트에 각 간선들의 흐름을 저장해 처리해준다.

 

사실 이렇게 노드의 간선을 인접행렬, 인접 리스트가 아닌 이동방법을 저장하는 약간 다른 방식으로 처리해본 적이 처음이라 과연 될 까 했는데, 다행히도 맞았습니다를 받을 수 있었다.