https://www.acmicpc.net/problem/24444
24444번: 알고리즘 수업 - 너비 우선 탐색 1
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방
www.acmicpc.net
https://www.acmicpc.net/problem/24445
24445번: 알고리즘 수업 - 너비 우선 탐색 2
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양
www.acmicpc.net
인접리스트, BFS
주의
1. 시간 초과 나왔던 부분:
- 문제에서 나온 알고리즘을 따라서 만들면 되지만 인접행렬로 코드를 짜게 되면 시간초과로 통과 할 수없었다. 인접 리스트로 코드를 작성해야 한다.
- C++ 개행 부분을 std::endl을 사용하면 시간초과가 뜬다..ㄷㄷ "\n"으로 사용해야 한다.
2. 무방향 그래프 이므로 양쪽으로 연결해줘야 한다.
3. 24445 번은 내림차순으로 정렬해줘야 한다. sort는 less<>가 default이기 때문에 greater<>를 사용해주거나 함수를 만들어서 적용해준다.
24445번 sort 부분만 다르기 때문에 24445번 첨부 합니다.
'📃 coding test > ◽ 백준' 카테고리의 다른 글
| (백준/c++) 11660 - 구간 합 구하기 5 (0) | 2022.06.23 |
|---|---|
| (백준/c++) 11659 - 구간 합 구하기 4 (0) | 2022.06.23 |
| (백준/c++) 24480 - 알고리즘 수업 - 깊이 우선 탐색 2 (0) | 2022.06.04 |
| (백준/c++) 24479 - 알고리즘 수업 - 깊이 우선 탐색 1 (0) | 2022.06.02 |
| (백준/c++) 17472번 - 다리만들기 (0) | 2022.05.25 |
안 하는 것 보다 낫겠지
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!
