링크 : https://school.programmers.co.kr/learn/courses/30/lessons/132266
코드
from collections import deque
def solution(n, roads, sources, destination):
world = [[] for _ in range(n+1)]
for s, e in roads:
world[s].append(e)
world[e].append(s)
visited = [-1] * (n+1)
visited[destination] = 0
q = deque([destination])
while q:
current = q.popleft()
for i in world[current]:
if visited[i] == -1:
visited[i] = visited[current] +1
q.append(i)
return list(visited[i] for i in sources)
아이디어
제한사항이
- 3 ≤ n ≤ 100,000
- 각 지역은 정수 1부터 n까지의 번호로 구분됩니다.
- 2 ≤ roads의 길이 ≤ 500,000
- roads의 원소의 길이 = 2
- roads의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b)
- 동일한 정보가 중복해서 주어지지 않습니다.
- 동일한 [a, b]가 중복해서 주어지지 않습니다.
- [a, b]가 있다면 [b, a]는 주어지지 않습니다.
2가지 경우에서 시간복잡도가 O(n)을 넘어가면 힘들 수도 있다고 생각했다. (보통 O(n)은 n이 천만이하일때, O(nlogn)은 n이 십만 이하일 때 통과된다고 하더라...) 그러면 다익스트라 알고리즘(O(V^2))은 안되니 고민...
결과적으로 기지에서 다른 모든 정점까지만 알면되서, 기지에서 다른 방문 가능한 모든 정점을 방문해서 얼마나 먼지만 알면 된다.
오류
처음에 위 아이디어로 코드를 작성했는데 계속 절반 넘는 테스트 케이스가 실패했다. 잘 보니 대체 왜 그랬는지는 모르겠지만 사용하는 큐를 우선순위큐를 쓰고 있어서 중복되는 간선을 모두 무시해서 발생한 문제로 확인.... 그냥 일반적으로 바꾸니 통과됐다...... 월드컵 때문인지 제정신이 아닌 것 같다...
추가로 아직 기초나 생각이 제대로 안잡혀서 그런지 문제 풀면서 아이디어는 나와도 코드로 작성이 힘들거나 아예 아이디어가 유추조차 안되는 문제가 많아 난이도 상관없이 다발적으로 그래서 조금씩이라도 공부를 해야겠다...
'알고리즘' 카테고리의 다른 글
백준(1644) - 소수의 연속합 (0) | 2022.12.12 |
---|---|
프로그래머스 - 신고 결과 받기 (0) | 2022.12.07 |
[Python] 백준 10989 - 수 정렬하기 3 (0) | 2022.10.10 |
[Python] 백준 1920번 수 찾기 (0) | 2022.10.10 |
[Programmers] Lv1. 시저 암호 (0) | 2022.09.28 |