백준 13905 파이썬1 13905. 세부 (Python) 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 풀이 모든 경로를 탐색해가면서 최대 개수를 구하면 시간초과가 발생한다. 따라서 처음부터 모든 경로를 탐색하는 것이 아니라 임의의 개수 k개를 혜빈이의 위치까지 들고갈 수 있는 경로가 있는지를 탐색하면 된다. 임의의 개수 k개는 이분 탐색을 사용하여 정할 수 있다. 즉, 이분 탐색과 BFS를 사용하여 문제를 해결하면 된다. 코드 import sys from collections import deque input = sys.s.. 2022. 6. 17. 이전 1 다음
