목록2023/12/19 (1)

클라우드 낚시꾼

[백준] 1260번 DFS와 BFS (Python)

시간 복잡도와 공간 복잡도 입력 조건에 "첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다." 라는 조건이 있었다. DFS와 BFS의 시간 복잡도는 O(|V+E|)이다. 그래서 문제의 조건에 따르면 최악의 경우 O(11000)이라는 시간 복잡도가 나온다. 시간 제한이 2초이고 파이썬이 1초에 2000만번 연산한다는 점을 고려해 봤을 때 시간 복잡도는 굉장히 널널하다. 알고리즘 문제에서 요구하는 것은 정보를 입력받아 그래프를 만들고, 낮은 노드를 우선 방문하는 조건으로 DFS, BFS 탐색하는 것이기에 알고리즘은 굉장히 단순하다. 아래는 자연어 알고리즘과 파이썬 코드이다. 1. 그래프 정보를 입력받아 저장한다. 2..
CodingTest/문제풀이 2023. 12. 19. 14:22
이전 Prev 1 Next 다음