목록2024/01/03 (1)

클라우드 낚시꾼

[백준] 24445번 알고리즘 수업-너비 우선 탐색 2 (BFS 시간 초과 해결)

문제 해결 과정 이 문제는 단순 BFS 문제였고, 인접 정점을 내림차순으로 정렬하는 조건이 중요했다. 문제가 쉬움에도 불구하고 나는 계속 답은 맞는데 시간 초과 문제가 발생했다. 그 이유는 아래와 같다. 시간 초과가 발생했던 이유 원래 필자는 그래프에 정보를 추가하면서 인접 정점을 정렬하였다. 그래서 정렬 과정이 2번 일어났고 이것이 시간 초과가 발생했던 주된 이유였다. 시간 초과 문제를 해결하기 위해 기존의 정렬 코드를 없애고 그래프 정렬을 위한 for문을 작성하여 정렬과정을 수행했다. 그 결과 정렬 코드의 시간 복잡도가 O(2n)에서 O(n)으로 감소하였다. 전체 코드 import sys from collections import deque input = sys.stdin.readline m,n,r ..
CodingTest/문제풀이 2024. 1. 3. 00:29
이전 Prev 1 Next 다음