투투

NxN의 맵이 있다. (0, 0)에서 출발해서 (N-1, N-1)까지 이동을 하려고하는데 중간중간에 도로들이 파손이 되어있다. 파손된 도로를 복구하는데 걸리는 시간은 각 칸에 적힌 수만큼 걸린다. 도로를 이동할 때 걸리는 시간을 제외하고 출발지부터 도착지까지 복구하면서 이동할 때 걸리는 시간이 최소인 시간을 구하라. 접근 - 기본적으로 다익스트라를 적용시켰다. - 2차원 맵이기 때문에 현재위치에서 상하좌우 칸에 대한 시간을 구하여 최솟값을 갱신해나간다. 구현 - 2차원 맵에 대한 정보를 입력받아 graph라는 2차원 리스트에 저장한다. - 이후 solve함수에서 해를 구하여 반환한다. - 다음은 solve함수에 대한 코드이다. - 먼저 각 칸을 INF로 초기화하여 나중에 최솟값으로 갱신될 수 있도록 한다..

어떤 도시에 E개의 일방통행 도로가 있고 각 구간이 만나는 연결지점에 0번부터 N번까지의 번호가 붙어있다. 이때 0번 지점에서 N번 지점까지 이동하는데 걸리는 최소한의 거리가 얼마인지 구하라. 다익스트라 알고리즘 - 다음 방문하는 노드에 대한 경로를 지금까지 기록한 정보를 통해 최솟값을 갱신한다. - 기록되어있는 정보에는 출발점부터 해당 번호까지 왔을 때의 최솟값이 저장되어있으며, 계속 갱신될 수 있다. 구현 - 2차원 리스트로 그래프를 표현한다. - 초기에 INF 값으로 초기화한 이유는 이후에 그래프를 탐색하면서 최솟값을 찾을 때 연결되어있지 않은 그래프는 최솟값의 후보에서 벗어나도록 하기위함이다. - E개의 일방통행 도로를 입력받아 그래프에 저장한다. V, E = map(int, input().spl..

0번부터 V번까지의 노드가 있고 E개의 간선이 주어지는 그래프가 있을 때 최소신장트리를 구성하는 가중치의 합을 출력한다. 프림 알고리즘 - 특정 정점을 시작으로 점진적으로 최소신장트리를 완성해나간다. - 지금까지 선택한 정점을 검색하여 아직 선택하지않은 정점 중에 가중치가 가장 적은 정점을 선택한다. 구현 - 정점의 개수(V)와 간선의 개수(E)를 입력받는다. - 간선의 개수만큼 노드a, 노드b, 가중치w를 입력받아 2차원 리스트로 그래프를 표현한다. V, E = map(int, input().split()) graph = [[0 for _ in range(V+1)] for _ in range(V+1)] for _ in range(E): a, b, w = map(int, input().split()) g..