문제 링크 https://www.acmicpc.net/problem/1389 문제 해설 Idea BFS 1부터 N까지의 번호에 대해 매번 BFS를 수행하면서 다른 모든 노드와의 거리를 파악 가장 작은 거리의 합을 가진 노드의 인덱스 번호를 출력 Time Complexity O(N^2+NM) = 510,000 Data Size N: 2 <= int <= 100 M: 1 <= int <= 5,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from collections import deque import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/1697 문제 해설 Idea BFS N에서 시작해 K에 도달할 때까지 x-1, x+1, x*2에 대한 최단거리를 탐색 두 점이 위치할 수 있는 범위 내에서 가까운 거리의 점부터 탐색을 수행 K에 대한 거리를 출력 N이 K보다 클 경우 x-1 외에는 이동수단이 없기 때문에 시간 단축을 위해 예외로 처리 Time Complexity O(N) = 100,000 Data Size N: 0 <= int <= 100,000 K: 0 <= int <= 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 from collections import deque def bfs(start, target): MAX = 10**5 count = [0] * (MAX+1) queue = deque([start]) while queue: x = queue....
문제 링크 https://www.acmicpc.net/problem/18352 문제 해설 Idea BFS 시작 노드 X부터 연결된 노드를 순차적으로 방문하면서 X로부터 떨어진 거리를 기록 거리가 K와 같은 노드를 출력하고, 해당하는 노드가 없을 경우 -1을 출력 거리가 K를 넘어가지 않는 노드에 대해서만 탐색하여 시간 단축 Time Complexity BFS: O(N+M) = 1,300,000 Data Size N: 2 <= int <= 300,000 M: 1 <= int <= 1,000,000 K: 1 <= int <= 300,000 X: 1 <= int <= N A, B: 1 <= int <= N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from collections import deque import sys input = sys....