반응형
문제
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
풀이
X번 노드에서 도달할 수 있는 도시들의 최단 거리를 구해야 합니다.
간선의 비용이 모두 동일하므로 BFS를 사용해서 풀이할 수 있는 문제입니다.
저는 visited라는 Int 배열을 선언하였고, 값을 X번 노드에서의 최단 거리로 사용하였습니다.
visited 배열 중 값이 k와 같은 노드를 출력시켜주었고, 없다면 -1을 출력하였습니다.
소스코드
후기
입력의 양이 많아서 빠른 입력을 사용해야 하나 했지만 괜찮았습니다.
BFS에 대한 이해가 있다면 풀이과정을 쉽게 떠올릴 수 있을 것 같습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 1543 문서 검색 (Swift) (0) | 2023.06.02 |
|---|---|
| [BOJ] 백준 3085 사탕 게임 (Swift) (0) | 2023.06.02 |
| [BOJ] 백준 2206 벽 부수고 이동하기 (Swift) (0) | 2023.05.31 |
| [BOJ] 백준 9205 맥주 마시면서 걸어가기 (Swift) (3) | 2023.05.26 |
| [BOJ] 백준 2162 선분 그룹 (Swift) (0) | 2023.05.25 |
