blog

2024-10-20-LGECT-3

Algorithm#Algorithm

문제

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


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


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

2024-10-20-LGECT-3 이미지 1
관공서 번호서류 번호
11, 2, 3
23, 5
31
43, 4
52, 4

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


  • 발급받아야 할 서류 개수 n
  • 관공서에서 발급 가능한 서류 정보를 담은 2차원 정수 배열 docs
  • 관공서 사이를 연결하는 길을 담은 2차원 정수 배열 roads
roadsm
[[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번 노드에서 출발해 모든 노드 방문 가능한 경우만 주어짐

입출력 예

docsn
[[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