문제 · 알고리즘 어려움 Python ·

Maximum bipartite matching

def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:

max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])  # -> 3
max_matching(2, 1, [[0, 0], [1, 0]])  # -> 1

• 1위Anthropic Claude Sonnet 5.5해결 · 테스트 11/11 통과응답 소요 9.7 초 · 실행 시간 453 ms · $0.02

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])기댓값 3	1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])기댓값 1	1 ms

  ✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 374 ms⏱ 69 ms
  코드

  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      adj = [[] for _ in range(n_left)]
      for u, v in edges:
          if 0 <= u < n_left and 0 <= v < n_right:
              adj[u].append(v)
      matchL = [-1] * n_left
      matchR = [-1] * n_right
      res = 0
      for u in range(n_left):
          for v in adj[u]:
              if matchR[v] == -1:
                  matchR[v] = u
                  matchL[u] = v
                  res += 1
                  break
      while True:
          dist = [-1] * n_left
          q = []
          for u in range(n_left):
              if matchL[u] == -1 and adj[u]:
                  dist[u] = 0
                  q.append(u)
          found = False
          qi = 0
          while qi < len(q):
              u = q[qi]
              qi += 1
              du = dist[u] + 1
              for v in adj[u]:
                  w = matchR[v]
                  if w == -1:
                      found = True
                  elif dist[w] == -1:
                      dist[w] = du
                      q.append(w)
          if not found:
              break
          it = [0] * n_left
          aug = 0
          for r in range(n_left):
              if matchL[r] != -1 or dist[r] != 0:
                  continue
              stack = [r]
              while stack:
                  u = stack[-1]
                  au = adj[u]
                  i = it[u]
                  pushed = False
                  done = False
                  while i < len(au):
                      v = au[i]
                      i += 1
                      w = matchR[v]
                      if w == -1:
                          it[u] = i
                          done = True
                          break
                      if dist[w] == dist[u] + 1:
                          it[u] = i
                          stack.append(w)
                          pushed = True
                          break
                  if done:
                      for x in stack:
                          v = adj[x][it[x] - 1]
                          matchL[x] = v
                          matchR[v] = x
                      aug += 1
                      break
                  if pushed:
                      continue
                  it[u] = i
                  dist[u] = -2
                  stack.pop()
          if aug == 0:
              break
          res += aug
      return res

• 2위MiniMax M3.1 Flash해결 · 테스트 11/11 통과응답 소요 5.9 초 · 실행 시간 691 ms · $0.0016

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])기댓값 3	2 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])기댓값 1	<1 ms

  ✓ 1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 10 ms✓ <1 ms✓ <1 ms⏱ 563 ms⏱ 106 ms
  코드

  from collections import deque
  
  
  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      if n_left == 0 or n_right == 0:
          return 0
  
      adj = [None] * n_left
      for u in range(n_left):
          adj[u] = []
      seen_sets = [set() for _ in range(n_left)]
      for e in edges:
          u = e[0]
          v = e[1]
          s = seen_sets[u]
          if v not in s:
              s.add(v)
              adj[u].append(v)
      for u in range(n_left):
          adj[u] = list(seen_sets[u])
  
      match_l = [-1] * n_left
      match_r = [-1] * n_right
      matching = 0
      INF = n_left + 1
  
      while True:
          # BFS layering
          dist = [-1] * n_left
          q = deque()
          for u in range(n_left):
              if match_l[u] == -1:
                  dist[u] = 0
                  q.append(u)
          limit = INF
          while q:
              u = q.popleft()
              du = dist[u]
              if du + 1 > limit:
                  continue
              for v in adj[u]:
                  w = match_r[v]
                  if w == -1:
                      if du + 1 < limit:
                          limit = du + 1
                  elif dist[w] == -1 and du + 1 < limit:
                      dist[w] = du + 1
                      q.append(w)
  
          if limit == INF:
              break
  
          ptr = [0] * n_left
  
          for root in range(n_left):
              if match_l[root] != -1 or dist[root] != 0:
                  continue
              # iterative DFS for an augmenting path
              stack = [root]
              rights = []  # rights[i]: right vertex used from stack[i] to stack[i+1]
              found = False
              while stack:
                  u = stack[-1]
                  a = adj[u]
                  advanced = False
                  i = ptr[u]
                  ln = len(a)
                  while i < ln:
                      v = a[i]
                      i += 1
                      w = match_r[v]
                      if w == -1:
                          if dist[u] + 1 == limit:
                              match_l[u] = v
                              match_r[v] = u
                              for k in range(len(stack) - 2, -1, -1):
                                  p = stack[k]
                                  rv = rights[k]
                                  match_l[p] = rv
                                  match_r[rv] = p
                              matching += 1
                              found = True
                              break
                      elif dist[w] == dist[u] + 1:
                          ptr[u] = i
                          stack.append(w)
                          rights.append(v)
                          advanced = True
                          break
                  if found:
                      break
                  ptr[u] = i
                  if not advanced:
                      dist[u] = -1
                      stack.pop()
                      if rights:
                          rights.pop()
  
      return matching

• 3위DeepSeek V4 Pro 0423미해결 · 테스트 9/11 통과응답 소요 2.8 초 · 실행 시간 1.2 초 · $0.0006

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])기댓값 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])기댓값 1	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ 시간 초과⏱ 시간 초과
  코드

  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      # Build adjacency list for left side
      graph = [[] for _ in range(n_left)]
      for u, v in edges:
          graph[u].append(v)
  
      # matchR[v] = u if job v is matched to worker u, else -1
      matchR = [-1] * n_right
  
      # Standard DFS for augmenting path (Kuhn's algorithm)
      def dfs(u, seen):
          for v in graph[u]:
              if seen[v]:
                  continue
              seen[v] = True
              if matchR[v] == -1 or dfs(matchR[v], seen):
                  matchR[v] = u
                  return True
          return False
  
      result = 0
      for u in range(n_left):
          # seen array for this DFS iteration
          seen = [False] * n_right
          if dfs(u, seen):
              result += 1
  
      return result

  2차 시도

  미해결 · 테스트 10/11 통과응답 소요 7.5 초 · $0.0013

  모델에게 실패한 테스트 수, 실패한 예시의 기댓값 및 반환값, 그리고 비공개 테스트의 입력값을 제외한 실패 원인만 제공되었습니다. 순위나 레이팅에는 반영되지 않습니다.

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])기댓값 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])기댓값 1	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 시간 초과⏱ 60 ms

  코드

  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      # Build adjacency (remove duplicates per worker)
      graph = [set() for _ in range(n_left)]
      for u, v in edges:
          graph[u].add(v)
      graph = [list(adj) for adj in graph]
  
      matchR = [-1] * n_right
  
      # DFS with pointer for visited tracking using iteration counter
      visited = [0] * n_right
      visit_counter = 0
  
      def dfs(u):
          nonlocal visit_counter
          for v in graph[u]:
              if visited[v] == visit_counter:
                  continue
              visited[v] = visit_counter
              if matchR[v] == -1 or dfs(matchR[v]):
                  matchR[v] = u
                  return True
          return False
  
      result = 0
      for u in range(n_left):
          visit_counter += 1
          if dfs(u):
              result += 1
  
      return result

• 4위Google Gemini 4 Argon미해결 · 테스트 8/11 통과응답 소요 10 초 · 실행 시간 3.2 초 · $0.0080

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])기댓값 3	2 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])기댓값 1	2 ms

  ✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✗ 시간 초과✓ 1 ms✓ <1 ms⏱ 시간 초과⏱ 시간 초과
  코드

  from collections import deque
  
  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      if n_left == 0 or n_right == 0 or not edges:
          return 0
  
      adj = [[] for _ in range(n_left)]
      for u, v in edges:
          adj[u].append(v)
  
      pair_u = [-1] * n_left
      pair_v = [-1] * n_right
      matching = 0
  
      # Greedy initialization
      for u in range(n_left):
          for v in adj[u]:
              if pair_v[v] == -1:
                  pair_u[u] = v
                  pair_v[v] = u
                  matching += 1
                  break
  
      dist = [0] * n_left
      INF = 10**9
  
      # Hopcroft-Karp algorithm
      while True:
          queue = deque()
          for u in range(n_left):
              if pair_u[u] == -1:
                  dist[u] = 0
                  queue.append(u)
              else:
                  dist[u] = INF
          
          found_augmenting_path = False
          while queue:
              u = queue.popleft()
              d_next = dist[u] + 1
              for v in adj[u]:
                  pu = pair_v[v]
                  if pu == -1:
                      found_augmenting_path = True
                  elif dist[pu] == INF:
                      dist[pu] = d_next
                      queue.append(pu)
          
          if not found_augmenting_path:
              break
              
          # Iterative DFS to avoid recursion limit and overhead
          for start_u in range(n_left):
              if pair_u[start_u] == -1:
                  stack = [(start_u, 0)]
                  while stack:
                      u, idx = stack[-1]
                      adj_u = adj[u]
                      n_adj = len(adj_u)
                      while idx < n_adj:
                          v = adj_u[idx]
                          pu = pair_v[v]
                          if pu == -1:
                              # Found augmenting path, trace back and flip edges
                              pair_v[v] = u
                              pair_u[u] = v
                              stack.pop()
                              while stack:
                                  parent_u, parent_idx = stack.pop()
                                  parent_v = adj[parent_u][parent_idx]
                                  pair_v[parent_v] = parent_u
                                  pair_u[parent_u] = parent_v
                              matching += 1
                              break
                          elif dist[pu] == dist[u] + 1:
                              stack[-1] = (u, idx)
                              dist[pu] = INF  # Mark visited in this phase
                              stack.append((pu, 0))
                              break
                          idx += 1
                      else:
                          stack.pop()
                          
      return matching

  2차 시도

  해결 · 테스트 11/11 통과응답 소요 17 초 · $0.01

  모델에게 실패한 테스트 수, 실패한 예시의 기댓값 및 반환값, 그리고 비공개 테스트의 입력값을 제외한 실패 원인만 제공되었습니다. 순위나 레이팅에는 반영되지 않습니다.

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])기댓값 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])기댓값 1	<1 ms

  ✓ <1 ms✓ 2 ms✓ <1 ms✓ 6 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 440 ms⏱ 73 ms

  코드

  from collections import deque
  
  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      if n_left == 0 or n_right == 0 or not edges:
          return 0
  
      adj = [[] for _ in range(n_left)]
      for u, v in edges:
          adj[u].append(v)
  
      pair_u = [-1] * n_left
      pair_v = [-1] * n_right
      matching = 0
  
      # Greedy initialization
      for u in range(n_left):
          for v in adj[u]:
              if pair_v[v] == -1:
                  pair_u[u] = v
                  pair_v[v] = u
                  matching += 1
                  break
  
      INF = 10**9
      unmatched = [u for u in range(n_left) if pair_u[u] == -1]
  
      while unmatched:
          dist = [INF] * n_left
          for u in unmatched:
              dist[u] = 0
          
          queue = deque(unmatched)
          min_free_dist = INF
          
          while queue:
              u = queue.popleft()
              d = dist[u]
              if d >= min_free_dist:
                  continue
              d_next = d + 1
              for v in adj[u]:
                  pu = pair_v[v]
                  if pu == -1:
                      min_free_dist = d_next
                  elif dist[pu] == INF:
                      dist[pu] = d_next
                      queue.append(pu)
          
          if min_free_dist == INF:
              break
              
          new_unmatched = []
          for start_u in unmatched:
              stack = [(start_u, 0, 0)]
              dist[start_u] = INF
              while stack:
                  u, idx, d = stack[-1]
                  adj_u = adj[u]
                  n_adj = len(adj_u)
                  d_next = d + 1
                  while idx < n_adj:
                      v = adj_u[idx]
                      pu = pair_v[v]
                      if pu == -1:
                          if d_next == min_free_dist:
                              pair_v[v] = u
                              pair_u[u] = v
                              stack.pop()
                              while stack:
                                  parent_u, parent_idx, _ = stack.pop()
                                  parent_v = adj[parent_u][parent_idx]
                                  pair_v[parent_v] = parent_u
                                  pair_u[parent_u] = parent_v
                              matching += 1
                              break
                      elif dist[pu] == d_next and d_next < min_free_dist:
                          stack[-1] = (u, idx, d)
                          dist[pu] = INF
                          stack.append((pu, 0, d_next))
                          break
                      idx += 1
                  else:
                      stack.pop()
                      if stack:
                          parent_u, parent_idx, parent_d = stack[-1]
                          stack[-1] = (parent_u, parent_idx + 1, parent_d)
              
              if pair_u[start_u] == -1:
                  new_unmatched.append(start_u)
                  
          unmatched = new_unmatched
  
      return matching

토큰 비용: $0.04 · 진행 방식 및 점수 산정 안내 →