[백준] 1031 스타대결 Python 3

파이썬을 사용하여 BFS(너비 우선 탐색) 알고리즘을 통해 최대 유량 문제를 해결하는 방법을 설명하겠습니다. 이 문제는 그래프 이론의 한 분야로, 네트워크 플로우 문제를 해결하는 데 사용됩니다. 주어진 문제를 해결하기 위해 작성한 Python 코드를 소개하고, 각 부분이 어떻게 동작하는지 자세히 설명하겠습니다.

문제 설명

주어진 문제는 다음과 같습니다:

• 두 개의 행렬 𝑁N과 𝑀M이 주어집니다.
• 각 행렬의 요소는 0 또는 1의 값을 가집니다.
• 목표는 𝑁×𝑀N×M의 0과 1로 이루어진 최종 행렬을 만들어 각 행과 열의 합이 주어진 값과 동일하게 만드는 것입니다.

이를 해결하기 위해서 네트워크 플로우 문제로 변환하고, BFS를 활용하여 최대 유량을 계산합니다.

코드 설명

다음은 문제를 해결하기 위해 작성한 Python 코드입니다.

 

from collections import deque

def bfs():
    # 시작점(0)에서 BFS로 경로를 탐색하여 도착점(K-1)에 도달하는지 확인
    dq = deque([0])
    parent = [-1] * K  # 부모 노드를 기록하는 배열
    while dq:
        now = dq.popleft()  # 현재 노드
        for next in adj[now]:  # 인접 노드 탐색
            # 방문하지 않은 노드이고, 잔여 용량이 있는 간선인 경우
            if parent[next] == -1 and graph[now][next] - flow[now][next] > 0:
                parent[next] = now  # 부모 노드 기록
                if next == K - 1:  # 도착점에 도달한 경우
                    return parent  # 부모 배열 반환
                dq.append(next)  # 다음 노드 큐에 추가
    return None  # 경로가 없는 경우

def update(i, j):
    # 특정 노드 i에서 j로의 경로를 찾는 BFS
    dq = deque([i])
    parent = [-1] * K  # 부모 노드를 기록하는 배열
    while dq:
        now = dq.popleft()  # 현재 노드
        for next in adj[now]:  # 인접 노드 탐색
            # 특정 조건을 만족하는 경우를 제외하고, 방문하지 않은 노드 탐색
            if (next > 0 and next < i) or (now == i and next <= j) or parent[next] != -1:
                continue
            if graph[now][next] - flow[now][next] > 0:  # 잔여 용량이 있는 간선
                parent[next] = now  # 부모 노드 기록
                if next == j:  # 목적지에 도달한 경우
                    return parent  # 부모 배열 반환
                dq.append(next)  # 다음 노드 큐에 추가
    return None  # 경로가 없는 경우

# 입력을 받아서 초기화
[N, M], row, column = [[*map(int, input().split())] for _ in range(3)]
K = N + M + 2  # 전체 노드 수 (출발점, 도착점 포함)
graph = [[0] * K for _ in range(K)]  # 그래프의 용량을 저장하는 배열
flow = [[0] * K for _ in range(K)]  # 흐름을 저장하는 배열
adj = [[] for _ in range(K)]  # 인접 리스트

# 행의 요구사항을 출발점과 연결
for i in range(1, N + 1):
    graph[0][i] = row[i - 1]  # 출발점에서 각 행으로의 용량
    adj[0].append(i)  # 인접 리스트 갱신
    adj[i].append(0)
    for j in range(1, M + 1):
        graph[i][j + N] = 1  # 각 행에서 각 열로의 용량
        adj[i].append(j + N)
        adj[j + N].append(i)

# 열의 요구사항을 도착점과 연결
for j in range(1, M + 1):
    graph[j + N][K - 1] = column[j - 1]  # 각 열에서 도착점으로의 용량
    adj[j + N].append(K - 1)
    adj[K - 1].append(j + N)

# 최대 유량 알고리즘 실행
while parent := bfs():
    now = K - 1  # 도착점부터 시작
    while now != 0:
        last = parent[now]  # 부모 노드 추적
        flow[last][now] += 1  # 정방향 간선에 유량 추가
        flow[now][last] -= 1  # 역방향 간선에 유량 감소
        now = last  # 현재 노드를 부모 노드로 갱신

# 모든 요구를 충족하는 경우 결과 출력
if sum(flow[0]) == sum(column) == sum(row):
    for i in range(1, N + 1):
        for j in range(N + 1, N + M + 1):
            if flow[i][j] and (parent := update(i, j)):
                flow[i][j] -= 1
                while j != i:
                    last = parent[j]
                    flow[last][j] += 1
                    flow[j][last] -= 1
                    j = last
    for i in range(1, N + 1):
        print(''.join(map(str, flow[i][N + 1:K - 1])))
else:
    print(-1)

코드 동작 원리

1. 입력 받기: 행렬의 크기 𝑁N, 𝑀M과 각 행과 열의 합을 입력받습니다.
2. 그래프 초기화: 노드의 개수 𝐾K를 계산하고, 그래프와 유량, 인접 리스트를 초기화합니다.
3. 그래프 구축: 소스에서 각 행으로의 간선과 각 행에서 열로의 간선, 그리고 열에서 싱크로의 간선을 설정합니다.
4. BFS 탐색: BFS를 통해 경로를 찾고, 경로가 존재하면 유량을 업데이트합니다.
5. 유량 검증 및 출력: 최대 유량이 행과 열의 합과 동일한지 검증하고, 동일하다면 최종 행렬을 출력합니다.