목록2025/05/08 (1)

잡다한 IT 지식

1249. SW 문제해결 응용 4일차 - 보급로

태그 잊지 않고 붙이세요#Algorithm #출제사이트 #D4 #Solved #Dijkstra문제 링크제한사항가장 첫 줄은 전체 테스트케이스의 수이다.각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.접근 방법문제엔 복구 시간이라고 쓰였지만 간선과 가중치로 단순하게 생각해보자.지도의 위치가 노드이며 복구 시간은 해당 노드로 이어진 간선의 가중치다.점과 점 사이 최소 거리로 문제를 단순화할 수 있다. 다익스트라로 해결 가능하다.복잡도시간복잡도: (V + E) * logE (V는 노드의 개수, E는 간선의 개수)공간복잡도: O(E)코드import heapqT = int(input())#..
알고리즘 문제 풀이 2025. 5. 8. 10:23
이전 Prev 1 Next 다음