https://www.acmicpc.net/problem/18352
18352번: 특정 거리의 도시 찾기
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개
www.acmicpc.net
> 문제 풀이 아이디어
bfs와 최단거리 유형으로 풀 수 있다.
- 시작점인 1을 큐(q)에 넣고 최단 거리정보를 나타낸 dist 리스트의 시작점엔 0을 넣는다.
- 1에서 갈 수 있는 노드는 2와 3이므로 이들을 q에 차례로 넣는다. 동시에 최단거리는 (0+1)로 dist의 각 인덱스에 추가해준다.
- 2에서 갈 수 있는 노드는 3과 4이지만, 3에는 이미 최소거리인 1이 들어가 있으므로 생략, 4에는 2까지의 거리인 1에 1을 더한 2를 dist에 넣어준다.
- q에 남은 3과 4 모두 이미 dist에 최소거리가 들어가 있기 때문에 생략
- q에 남은 요소가 없으므로 while 반복문을 종료시킨다.
> 포인트
dist에 있는 값이 inf가 아닌 경우, bfs알고리즘으로 이미 최소거리가 들어가있는 것이기 때문에 추가적인 연산을 해주지 않았다.
> 코드
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| [백준 | 파이썬3] 18352 병사 배치하기 (0) | 2022.07.07 |
|---|---|
| [백준 | 파이썬3] 1874 스택 수열 (0) | 2022.02.28 |
| [백준 | 파이썬3] 10814 나이 순 정렬 (0) | 2022.02.23 |
| [프로그래머스 | 파이썬3] 약수의 개수와 덧셈 (0) | 2021.12.09 |
| [프로그래머스 | 파이썬3] 실패율 - 정렬 (0) | 2021.12.08 |