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로 문제를 풀었는데, 시간초과가 발생했다. 시간초과 해결에 결정적인 도움을 준 생각이 아래의 생각이다. 만약, 도시가 300,000개 있을 때, 1 -> 2 -> 3 -> ... -> 300,000 까지 이어진 단방향 도로가 있다. 시작 도시가 2 이고, 거리가 2인 도시를 구해야 할 경우 정답은 4밖에 없다. 근데 이럴 경우 내가 300,000 번째 도시까지 가야할 이유가 있을까..

1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 양방향으로 이어져있는 노드들 사이에서, 예를들어 내가 1일때 1. 2~N 까지 갈 수 있는 최단거리를 구한 다음 2. 그 최단 거리들을 전부 합한게 1의 케빈 베이컨의 수 3. 1~N 의 케빈 베이컨의 수가 가장 작은 사람을 구하는 문제. 각 숫자까지의 최단거리를 기록해줘야 했다. 이전 숫자까지 간 거리 + 1 을 해준 것이 최단거리이기 때문. 노드간 최단경로를 구할 수 있는 알고리즘엔 플로이드워셜, 다익스트..