목록BFS (1)
체뚱로그
[백준/C++] 18352 - 특정 거리의 도시 찾기
풀이 시간: 01:38:37 시간 복잡도: O(M+N*N+N) = O(N^2) 단방향 경로 추가 O(M) + while문은 큐가 비어있을 때까지 반복하므로, 최악의 경우 모든 도시를 방문 O(N) * for문은 현재 도시와 연결된 도시 확인, 최악의 경우 한 도시에 모든 도시가 연결 O(N) + result 값 출력, 최대 N이므로 O(N) 공간 복잡도: O(N*M+N) = O(NM) one_way_route 크기 O(M) + result의 최대 크기는 N이므로 O(N) + shortest_route 크기 O(N) 참고 자료: https://kimjingo.tistory.com/57 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 ..
PS/BOJ
2023. 12. 19. 00:45