(백준 12834 주간 미팅

• tags : (algorithm

  No matching post could be found

  - (BFS
• 문제 링크 : https://www.acmicpc.net/problem/12834
• 풀이 링크
  • Python

• 각 참여자들이 두 지점까지의 최단 거리의 합의 합을 구해야한다.
  • 조금 풀어서 다시 설명하면,
  • 각 참여자 위치에서 두 지점까지의 최단 거리의 합을 구해야 하고,
  • 이 거리의 합을 모두 합하여 출력하면된다.
• 각 지점에서 시작해서 목적지 두 지점까지 거리를 구해도 되지만,
  • 탐색이 많아지면 많은 시간이 걸릴 수 있다.
• 대신, 목적지로 하는 두 지점에서 시작하여, 다른 모든 지점까지 거리를 구하고, 각 참여자는 두 위치까지 이미 구한 거리를 바로 가져와서 사용하면 된다.

def search(V: int, start: int, roads: Road) -> list[int]:
    dist = [-1] * (V + 1)
    queue = deque([(start, 0)])
    while queue:
        x, d = queue.popleft()
        if -1 != dist[x] <= d:
            continue
        dist[x] = d
        for y, _d in roads[x]:
            if -1 == dist[y] or dist[y] > d + _d:
                queue.append((y, d + _d))
    return dist

• KIST와 씨알푸드에서 모든 점까지 위치를 구해야하는데, 완전히 같은 방식을 사용한다.
  • 그래서 BFS를 2회 실행하는 대신, 하나의 함수를 생성하고, start변수만 처리하여 구했다.
• 또한, 거리를 구할 수 없으면 -1이라 하였는데, 이후 if문을 통하여 처리하는 대신 거리를 -1로 초기화하여 구했다.
  • 함수 내부 두개의 if문에서 거리에 대한 조건이 조금 까다로워 지지만,
  • 추가적인 리스트 순회 또는 출력에서 if문을 사용하지 않아도 된다.
  • 메모리 측면에서는 조금 더 이점이 있을 것 같고, 시간은 비슷할것으로 보인다.

ans = sum([from_kist[h] + from_ssial[h] for h in teammates])

• 출력 값은 한 줄로 빠르게 구했다.