목차
- 바둑돌
1. 바둑돌
문제
당신은 N x N 의 격자 형식의 종이 위에 친구와 바둑과 유사한 놀이를 하였다.
이 놀이의 결과로 바둑돌은 격자 위라면 어디에도 놓여있을 수 있으며, 바둑돌이 없어 연필로 그려져 있다.
이제 한 게임이 끝나고, 다음 게임을 하기 위해서 당신은 연필로 그려진 바둑돌을 모두 지우려고 한다.
지우개질은 행 또는 열로 격자를 따라서 할 수 있다.
예를 들어 3열을 따라 지우개질을 하면, 3열 위에 있는 모든 바둑돌이 지워진다.
격자 위에 놓여진 바둑돌의 위치가 stones[t] = [행, 열] 로 주어질 때, 모든 바둑돌을 제거하기 위한 최소의 지우개질 횟수를 구하시오.
입력 설명
0 < N ≤ 1000 < stones.length ≤ 1000
출력 설명
최소의 지우개질 횟수를 정수로 반환
매개변수 형식
N = 6- stones =
[[0, 1], [0, 2], [5, 3], [4, 3]]
반환값 형식
2
입출력 예시 설명
0행을 따라 지우개질을 하고,3열을 따라 지우개질을 하면 된다.
풀이
이 문제는 네트워크 플로우(NetworkFlow)중 이분그래프(Bipartite Graph)의 최대매칭(Maximum bipartite matching)에 속한다.
네트워크 플로우(Network Flow)
- 특정지점에서 다른지점까지 얼마나 많은 데이터가 흘러갈 수 있는지 측정하는 방법으로 네트워크에서 흐를 수 있는 유량(flow)를 정의하고 이것을 최대화/최소화 등을 해결하는 알고리즘
최대유량 문제(Maximum Flow)
- 주어진 네트워크에서 시작점에서 도착점으로 흐를 수 있는 유량의 최대값을 구하는 문제
- BFS기반의 에드몬드 카프(Edmond-Karp)알고리즘을 사용한다.
- 유량(Flow): 네트워크 상의 각 간선들을 통해 실제로 흐르고 있는 값(유량)을 타나낸다.
- ex) 아래 그림에서 7과 5가 유량
- 용량(Capacity): 간선이 처리할 수 있는 최대 한도(유량은 용량의 범위 내에서만 존재한다)
- ex) 아래 그림에서 10, 5가 용량
그림 설명
- 용량
- 0 → 1 간선용량: 10
- 1 → 2 간선용량: 5
- 유량
- 0 → 1 간선을 통해 7이 흐른다
- 1 → 2 간선을 통해 5가 흐른다
- 1 →2 간선을 통해 7을 보낼 수 없다. 왜냐하면 1 → 2의 용량이 5이기 때문이다.
아래는 에드몬드 카프(Edmond-Karp) 알고리즘을 사용하여 네트워크의 최대 유량을 계산하는 알고리즘이다.
from collections import deque
def edmonds_karp(capacity, source, sink):
"""
에드몬드-카프 알고리즘으로 최대 유량 계산
:param capacity: 용량을 나타내는 그래프 (인접 행렬 형태)
:param source: 시작 노드 (source)
:param sink: 종료 노드 (sink)
:return: 최대 유량 (int)
"""
n = len(capacity)
flow = [[0] * n for _ in range(n)] # 현재 유량
total_flow = 0 # 최대 유량
while True:
# BFS로 증가 경로를 찾는다
parent = [-1] * n # 증가 경로를 추적하기 위한 리스트
parent[source] = source
queue = deque([source])
while queue:
current = queue.popleft()
for next_node in range(n):
# 잔여 용량이 있고, 방문하지 않은 노드만 탐색
if capacity[current][next_node] - flow[current][next_node] > 0 and parent[next_node] == -1:
parent[next_node] = current
queue.append(next_node)
# 종료 노드에 도달하면 BFS 종료
if next_node == sink:
queue = []
break
# 종료 노드(sink)에 도달하지 못하면 루프 종료
if parent[sink] == -1:
break
# 증가 경로에서 최소 잔여 용량 찾기
path_flow = float('Inf')
node = sink
while node != source:
prev_node = parent[node]
path_flow = min(path_flow, capacity[prev_node][node] - flow[prev_node][node])
node = prev_node
# 증가 경로를 따라 유량을 업데이트
node = sink
while node != source:
prev_node = parent[node]
flow[prev_node][node] += path_flow
flow[node][prev_node] -= path_flow # 역방향 간선
node = prev_node
# 최대 유량 증가
total_flow += path_flow
return total_flow
# 예제 실행
if __name__ == "__main__":
# 그래프의 용량(capacity) 행렬
# 노드: 0(S), 1, 2, 3, 4, 5(T)
capacity = [
[0, 10, 10, 0, 0, 0], # 노드 0
[0, 0, 2, 4, 8, 0], # 노드 1
[0, 0, 0, 0, 9, 0], # 노드 2
[0, 0, 0, 0, 0, 10], # 노드 3
[0, 0, 0, 6, 0, 10], # 노드 4
[0, 0, 0, 0, 0, 0], # 노드 5
]
source = 0 # 시작 노드
sink = 5 # 종료 노드
# 최대 유량 계산
max_flow = edmonds_karp(capacity, source, sink)
print("최대 유량:", max_flow)노드들 용량과 함께 예시로 그리면 아래와 같다.
위 코드를 통해 아래 그램처럼 총 4개의 경로를 탐색하여 최대 유량을 계산한다.
따라서 while True 조건을 4번반복한다.
따라서 최대 유량은 시작노드(Source)의 총 합인 19가 된다.
이분 매칭(Bipartite Matching)
- 매칭: 이분 그래프에서 한 정점이 다른 하나의 정점과만 짝지어진 것(한 정점이 여러 정점과 짝지어질 수 없음)
- 한 사람은 여러 사람과 동시에 짝을 이룰 수 없다.
- 최대 매칭: 그러한 매칭중 간선의 수가 가장 많은 매칭
- 가장 많이 둘씩 짝을 이룰 수 있는 방법
이제 바둑돌 문제로 들어가보자.
바둑돌 문제는 최대 이분 매칭으로 풀 수 있다.
만약 바둑돌이 아래와 같을 때 이를 시각화하면 다음과 같다.
N = 6- stones =
[[0, 1], [0, 2], [5, 3], [4, 3]]
왼쪽 그룹이 행, 오른쪽 그룹이 열이라 보면 된다.
0행은 1열과 2열이 짝을 맺을 수 있지만 하나만 선택할 수 있음으로 여기서는 1이, 4는 3이 각각 선택되어 최대 간선의 갯수 2개가 정답이된다.
전체 코드는 아래와 같다.
from collections import defaultdict
def solution(n, m, edges):
"""
이분 그래프의 최대 매칭을 찾는 함수 (DFS 기반).
:param n: 왼쪽 정점의 개수 (U 그룹)
:param m: 오른쪽 정점의 개수 (V 그룹)
:param edges: 간선 리스트 [(u, v), ...] (0-indexed)
:return: 최대 매칭 수
"""
# 인접 리스트 생성
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 매칭 결과를 저장할 배열
match_u = [-1] * n # U 그룹의 매칭 결과
match_v = [-1] * m # V 그룹의 매칭 결과
def dfs(u):
"""DFS를 사용하여 증가 경로를 찾고, 매칭을 갱신하는 함수"""
if visited[u]:
return 0
visited[u] = True
for v in graph[u]:
# v가 매칭된 적이 없거나, v와 연결된 노드에서 증가 경로 탐색 가능하면 매칭
if match_v[v] == -1 or dfs(match_v[v]):
match_u[u] = v
match_v[v] = u
return True
return False
# 최대 매칭 찾기
max_match = 0
for u in range(n):
visited = [False] * m # 각 DFS마다 방문 여부 초기화
if dfs(u):
max_match += 1
return max_matchTestcase
# 테스트 1
입력값 〉 6, [[0, 1], [0, 2], [5, 3], [4, 3]]
기댓값 〉 22.
문제
제한시간: 10초
당신에게 2차원 평면상에 있는 점의 좌표가 정수 배열 x[i]와 y[i]에 각각 x좌표와 y좌표
가 주어졌다.
이 2차원 평면상의 점은 x좌표가 엄격하게 증가하는 수열이다.
즉, 모든 i < j 에 대해서 x[i] < x[j] 이다.
위 점 중 |x[i] - x[j]| ≤ k 를 만족하는 i, j (i < j) 중에서,
가능한 최대의 y[i] + y[j] + |x[i] - x[j]|의 값을 구하시오.
입력 설명
- 2 ≤ x.length = y.length ≤ 100000
- -100000 ≤ x[i], y[i] ≤ 100000
- 0 ≤ k ≤ 1000
출력 설명
가능한 최대의 값을 정수로 반환
매개변수 형식
- x = [1, 2, 5, 6]
- y = [3, 1, 10, -9]
- k = 2
반환값 형식
5
예시입출력 설명
i = 0, j = 1 일 때 3 + 1 + |1 - 2| = 5 로 최대값이 된다.
풀이
이 문제는 힙큐를 사용해 빠르게 O(nlogn) 의 풀이 속도로 풀었다.
이중 포문을 사용하여 O(n^2)으로 풀이하면 풀리지 않는다.
왜냐하면 1초 : 1억번 = 10초 : 10억번(10^9) 임으로 대략 10억번의 연산 이하로 풀이되어야 하는데
n의 값은 최대 100,000번이된다 100,000 x 100,000 = 10^10 이다.
따라서 모든 경우의 수를 다 탐색하려는 이중포문의 접근법은 지양해야한다.
좀 더 효율적으로 풀기 위해 힙큐를 사용했으며 힙큐에 담긴값은 i라고 볼 수 있고 반복문에서 매번 바뀌는 i는 j라고 이해하면 된다.
몇가지 핵심 포인트를 알아보자
i < j 에 대해서 x[i] < x[j] 조건에 의해
y[i] + y[j] + |x[i] - x[j]| 의 값을 y[i] + y[j] + x[j] - x[i] 형태로 절대값을 풀 수 있다.
그리고 i인덱스와 j인덱스로 정리해보면: y[i] - x[i] + y[j] + x[j] 로 쓸 수 있다.(i < j)
따라서 빈 max_heap에 (a)y[i] - x[i]값과 (b)x[i] 두 값을 함께 큐에 넣는다.
- (a): max_val 계산을 하기 위해서는 저 값이 최대인 경우 현재 시점을 j라할 때(y[j] + x[j]) 최대값을 가질 수 있기 때문에 음수(-)를 취해주어 최대값을 큐에서 뽑도록 한다.
- max_val을 구할 때 heapq.pop을하면 안되는 이유는 현재 시점(j)가 계속 변해감에 따라 최대값이 달라질 수 있기 때문이다.
- (b):
|x[i] - x[j]| ≤ k이 조건 또한x[j] - x[i] ≤ k로 바꿀 수 있고 이 조건을 확인하기 위해 현재시점이 j라면 이전시점 i들을 담는 것이다.
이를 코드로 나타내면 아래와 같다.
import heapq
def solution(x, y, k):
max_val = float('-inf') # ① 결과(최대값) 저장용
max_heap = [] # ② 최대 힙(우선순위 큐)
n = len(x)
for i in range(n):
# ③ 문제 조건: |x[i] - x[j]| > k 인 경우는 제외
# max_heap에 어떤 값이 들어가 있었다면 이는 i보다 작은 값을 의미
# 즉, x[j] - x[i] > k 와 동일
while max_heap and x[i] - max_heap[0][1] > k:
heapq.heappop(max_heap)
# ④ 힙의 최댓값을 사용하여 현재 i에 대한 최대값 갱신
if max_heap:
# max_heap[0] = ( -(y[j]-x[j]), x[j] )
# => -max_heap[0][0] = (y[j]-x[j])
max_val = max(max_val, y[i] + x[i] + (-max_heap[0][0]))
# ⑤ 지금의 i에 대응하는 (y[i]-x[i]) 값을 힙에 넣는다.
heapq.heappush(max_heap, (-(y[i] - x[i]), x[i]))
return max_valTestcase
# 테스트 1
입력값 〉 [1, 2, 5, 6], [3, 1, 10, -9], 2
기댓값 〉 5
# 테스트 2
입력값 〉 [4, 12, 15, 19, 21, 25], [8, -4, 7, 1, 4, -9], 4
기댓값 〉 12출처
해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.
모든 자료는 저작권법에 의하여 보호받는 저작물로서 이에 대한 무단 복제 및 배포를 원칙적으로 금합니다.
Comment