Dijkstra

오랜만에 포스팅~~   푼 날짜 : 2024.12.20푼 문제 : [22116] / 창영이와 퇴근사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :처음 문제를 풀 때 실수했던 것은 최대라는 말을 빼먹구 코드를 짠 것.. 창영이가 지날 수 있는 최대 경사의 최솟값을 알아야만 한다.  "최대 경사" 를 구하는 문제이다.따라서 경사가 없다고 그냥 0을 출력하면 안된다는 얘기...  백준 게시판에서 주워온 반례를 첨부한다.320 15 205 10 202 1 0 답은 0이 아니라 5다.5 따라서 최대 경사 max를 구하면서 그 값이 가장 작은 수를 구하는 코드를 짜야한다!   코드 :import sysimport heapqinput = sys.stdin.readlineINF = fl..

푼 날짜 : 2024.11.20푼 문제 : [2665] / 미로만들기사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :4방향 탐색을 하며 최소로 방을 변경하는 횟수를 누적해 주었다.이 문제에서는 1이 흰방, 0이 검은 방인데 검은방-> 흰방을 계산해야 해서 0과 1을 바꿔주는 작업이 필요했다. now_color = 0 if int(graph[ny][nx]) else 1all_cost = now_cost + now_color 따라서 위 처럼 현재 컬러에 따라 0인지 1인지 바꾸어서 누적값을 계산했다.  코드 :import sysimport heapqinput = sys.stdin.readlineINF = float("INF")dy = [-1, 1, 0, 0]dx = [0, 0..

푼 날짜 : 2024.11.19푼 문제 : [4485] / 녹색 옷 입은 애가 젤다지?사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :N이 0일 때까지 반복하므로 while True에서 N 값에 따라 break를 넣어주었다. 현재위치가 x, y 일때 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 모두 탐색 가능하므로 4방향 탐색을 진행한다.이때 값이 더 작은 경우 업데이트 해주고 아니라면 넘어간다.  코드 :import sysimport heapqinput = sys.stdin.readlineINF = float("INF")dy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]def dijkstra(N, graph): heap = [..

푼 날짜 : 2024.11.14푼 문제 : [17396] / 백도어사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :시야가 있는 곳은 계산하지 않고 넘기는 방식에 일반적인 다익스트라 방식으로 계산했다.  코드 :import sysimport heapqinput = sys.stdin.readlineINF = float("INF")N, M = map(int, input().split())ward = list(map(int, input().split()))graph = [[] for _ in range(N)]for _ in range(M): a, b, t = map(int, input().split()) graph[a].append((b, t)) graph[b]...

푼 날짜 : 2024.11.16푼 문제 : [1261] / 알고스팟사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :현재위치가 x, y 일때 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 모두 탐색 가능하므로 4방향 탐색을 진행한다.이때 값이 더 작은 경우 업데이트 해주고 아니라면 넘어간다. 최종 목적지까지 반복하면 벽을 최소한으로 부순 값을 알 수 있다.   코드 :import sysimport heapqN, M = map(int, sys.stdin.readline().split())graph = []for _ in range(M): lst = list(sys.stdin.readline().rstrip()) graph.append(lst)..

푼 날짜 : 2024.11.15푼 문제 : [23793] / 두 단계 최단 경로 1사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 : 1) (X -> Y) + (Y -> Z) 계산2) X -> Z 계산 (이때 Y는 지나가면 안된다. ) 따라서 아래와 같이 계산을 해서 답을 구했다. XY = dijkstra(X) # X -> Y 계산YZ = dijkstra(Y) # Y -> Z 계산 XZ = dijkstra(X, True) # X -> Z (Y는 지나가면 안됨) 그리고 답이 INF인 경우 -1을 출력했다.  코드 :import sysimport heapqinput = sys.stdin.readlineINF = float("INF")N, M = map(int, input().s..

푼 날짜 : 2024.11.15푼 문제 : [18223] / 민준이와 마산 그리고 건우사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :두 개의 경로를 계산해서 계산 값이 일치한다면 "SAVE HIM" 아니라면 "GOOD BYE"를 출력했다. 1) 민준(1) -> 마산(V)2) 민준(1)-> 건우(P) -> 마산(V)   코드 :import sysimport heapqV, E, P = map(int, sys.stdin.readline().split())graph = [[] for _ in range(V+1)]for _ in range(E): A, B, C = map(int, sys.stdin.readline().split()) graph[A].append((B, ..

푼 날짜 : 2024.11.14푼 문제 : [2211] / 네트워크 복구사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :다익스트라를 사용하여 최소비용을 계산한다.최소비용을 계산하며 어디서 출발해서 어디로 연결되는지(연결되는 A, B)를 같이 저장했다.이후 해당 연결된 A, B를 출력했다. 아래와 같은 예제를 살펴보면,4 51 2 11 4 41 3 24 2 24 3 3 그래프는 아래와 같이 그려지며 최단 비용으로 연결하는 것은 노란색과 같다.  코드 :import sysimport heapqN, M = map(int, sys.stdin.readline().split())graph = [[] for _ in range(N+1)]for _ in range(M): A, B,..