2146번 - 다리 만들기
채점 중간 쯤에서 시간 초과가 납니다.
기본 아이디어는 dfs로 컴포넌트를 찾고 각 컴포넌트마다 bfs를 돌려서 다른 컴포넌트에 도착했을 때 min 값을 찾는 방식으로 구현했습니다.
dfs, bfs 둘 다 stack, queue 반복문으로 돌려서 시간 복잡도는 O(N^2) 이라고 생각했는데 어디서 시간 초과가 나는 걸까요?
고수님들의 도움 부탁드립니다.
댓글을 작성하려면 로그인해야 합니다.
qorgkr26 2년 전
채점 중간 쯤에서 시간 초과가 납니다.
기본 아이디어는 dfs로 컴포넌트를 찾고 각 컴포넌트마다 bfs를 돌려서 다른 컴포넌트에 도착했을 때 min 값을 찾는 방식으로 구현했습니다.
dfs, bfs 둘 다 stack, queue 반복문으로 돌려서 시간 복잡도는 O(N^2) 이라고 생각했는데 어디서 시간 초과가 나는 걸까요?
고수님들의 도움 부탁드립니다.