(백준 1045 도로

• tags : (algorithm

  No matching post could be found

  (MSP
• 문제 링크 : https://www.acmicpc.net/problem/1045
• 풀이 링크
  • Python

• 기본적으로 MSP를 찾아야 하는 문제
  • 추가적으로 원하는 수만큼 도로를 더 찾아야 한다.
• MSP를 구하는 다양한 방법 모두 적용할 수 있을 것 같고, union-find를 활용했다.
• 각 도로를 탐색하면서 연결하지 않은 도로는 따로 저장하여 원하는 수의 도로를 맞추기 위해 도로를 추가한다.

roads_sets = []
unused = []
parents = list(range(N))
for i in range(N):
    for j in range(i + 1, N):
        if roads[i][j] == "N":
            continue
        x, y = find_parent(parents, i), find_parent(parents, j)
        if x == y:
            unused.append((i, j))
            continue
        roads_sets.append((i, j))
        parents = union_parents(parents, x, y)

• 인접 행렬에서 도로를 찾고, 연결, 쓰지 않는 도로 저장까지 한번에 진행했다.
• roads_sets은 MSP를 만족하기 위한 도로를 저장했고, MSP를 만드는 조건에 맞지 않는 도로는 unused에 저장했다.
• 도로 탐색은 문제 조건에 따라 (A, B)일 때 A < B인 조건으로 탐색했고,
  • 이후 union-find를 진행하며 union 조건에 맞으면 roads_sets에, 아니면 unused에 저장

if len(roads_sets) < N - 1 or len(roads_sets + unused) < M:
    print(-1)
else:
    ans = [0] * N
    for x, y in roads_sets:
        ans[x] += 1
        ans[y] += 1
    for i in range(M - (N - 1)):
        x, y = unused[i]
        ans[x] += 1
        ans[y] += 1

• 모든 도시를 연결하지 못하거나, 도로의 개수가 M개가 안되면 -1을 출력
• 아니라면 우선 MSP를 이루는 도로를 추가하고, 사용하지 않는 도로들 중 먼저 저장한 것 순서대로 추가한다.
  • 문제 조건에서 도로의 우선순위를 만족시키기 위함.