🔥

문제

1 ~ n번으로 분류되는 n가지 서류를 발급받기 위해 관공서에 방문하려고 한다. 1 ~ m번까지 m개의 관공서가 있고, 각 관공서에서 발급한 서류 종류가 정해져 있다. 관공서에 방문하면 개수 제한 없이 원하는 서류를 발급받을 수 있다.


집과 관공서들 사이를 연결하는 길을 나타내는 무방향 그래프가 주어진다. 그래프는 m + 1개의 노드로 이루어져 있으며, 0번은 당신의 집을 나타내고 1 ~ m번 노드는 순서대로 1 ~ m + 1번 관공서를 나타낸다. 노드 사이를 연결하는 간선은 길을 나타낸다. 모든 길은 양방향으로 통과 가능하고 길을 지나는데 필요한 이동 거리는 1이다.


집에서 출발하여 모든 서류를 발급받고 집으로 돌아오는데 필요한 최소 이동거리는?

관공서 번호 서류 번호
1 1, 2, 3
2 3, 5
3 1
4 3, 4
5 2, 4

0 -> 2 -> 4 -> 1 -> 4 -> 0 순으로 이동하면 모든 서류 발급 가능
2번에서 3, 5 발급
4번에서 4 발급
1번에서 1, 2 발급


  • 발급받아야 할 서류 개수 n
  • 관공서에서 발급 가능한 서류 정보를 담은 2차원 정수 배열 docs
  • 관공서 사이를 연결하는 길을 담은 2차원 정수 배열 roads
roads m
[[0, 2], [0, 3], [0, 4], [1, 4], [2, 3], [2, 4], [3, 5], [4, 5]] 5
[[0, 1], [1, 2], [2, 3], [3, 4], [1, 7], [2, 5], [5, 6], [4, 7], [0, 5]] 7

제한사항

  • 3 <= n <= 8
  • 3 <= docs의 길이 = m <= 100
    • docs[i]의 길이 n
    • docs[i][j]는 0 또는 1
      • 1은 i + 1번 관공서에서 j + 1번 서류 발급 가능함
      • 0은 i + 1번 관공서에서 j + 1번 서류 발급 불가능함
  • m <= roads의 길이 <= 300
    • roads의 원소는 [a, b] 형태로 a번 노드와 b번 노드를 연결하는 간선이 존재함을 의미
  • 0 <= a <= b <= m
    • roads의 원소는 중복 X. 0번 노드에서 출발해 모든 노드 방문 가능한 경우만 주어짐

입출력 예

docs n
[[1, 1, 1, 0, 0], [0, 0, 1, 0, 1], [1, 0, 0, 0, 0], [0, 0, 1, 1, 0], [0, 1, 0, 1, 0]] 5
[[0, 0, 1, 0], [0, 1, 0, 1], [0, 0, 0, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 1, 1, 1], [0, 0, 0, 0]] 4

Source

from collections import deque
# n: 서류의 개수, m: 관공서의 수
def min_distance_to_collect_docs(n, m, docs, roads):
    # 그래프 구성
    graph = [[] for _ in range(m + 1)]
    for a, b in roads:
        graph[a].append(b)
        graph[b].append(a)

    # 관공서에서 발급 가능한 서류 정보를 비트마스크로 변환
    office_docs = [0] * (m + 1)  # 집(0번 노드) 포함
    for i in range(m):
        for j, can_issue in enumerate(docs[i]):
            if can_issue:
                office_docs[i + 1] |= (1 << j)

    # BFS 초기화
    queue = deque([(0, 0, 0)])  # (현재 노드, 발급 상태, 이동 거리)
    visited = set()
    visited.add((0, 0))  # (노드, 상태)
    all_docs_mask = (1 << n) - 1  # 모든 서류를 발급받은 상태

    while queue:
        node, state, distance = queue.popleft()

        # 모든 서류를 발급받은 경우
        if state == all_docs_mask and node == 0:
            return distance

        # 현재 노드에서 발급 가능한 서류 추가
        new_state = state | office_docs[node]

        # 인접 노드 탐색
        for neighbor in graph[node]:
            if (neighbor, new_state) not in visited:
                visited.add((neighbor, new_state))
                queue.append((neighbor, new_state, distance + 1))

# 테스트 케이스
print(min_distance_to_collect_docs(
    5, 5,
    [[1, 1, 1, 0, 0], [0, 0, 1, 0, 1], [1, 0, 0, 0, 0], [0, 0, 1, 1, 0], [0, 1, 0, 1, 0]],
    [[0, 2], [0, 3], [0, 4], [1, 4], [2, 3], [2, 4], [3, 5], [4, 5]]
))  # 출력: 5

print(min_distance_to_collect_docs(
    4, 7,
    [[0, 0, 1, 0], [0, 1, 0, 1], [0, 0, 0, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 1, 1, 1], [0, 0, 0, 0]],
    [[0, 1], [1, 2], [2, 3], [3, 4], [1, 7], [2, 5], [5, 6], [4, 7], [0, 5]]
))  # 출력: 7

참고