Dijkstra 3

[백준24042/골드1] 횡단보도 - Python

https://www.acmicpc.net/problem/24042 횡단보도 프로젝트를 진행하면서 이런식으로 알고리즘을 짜면 좋겠다 싶은 생각을 했는데 비슷한 문제가 있어서 풀어봤다. ✅ 문제 조건1. 교차로의 구역 : N개2. 주어진 횡단보도의 전체 주기 : M분 (M개의 연결 노드, 1분간격으로 바뀜)3. 0분에 출발해서 1번 구역에서 N번 구역까지 이동하는 최소 시간 구하기 ✅ 접근 방식일단 다른 다익스트라랑 똑같이 풀되, 가중치 계산이 따로 필요하다고 생각했다.현재 시간, 현재 노드에서 이동할 수 있는 다른 연결 노드 중, 언제 출발할 수 있는지 (신호등이 언제 켜지는지) 계산이 필요했다. 알아야할 값1. 연결된 노드 중 신호등이 켜지는 시간 (기다리는 시간)2. 1에서 구한 기다리는 시간에서 ..

algorithm/Dijkstra 2025.05.09

[백준1504/골드4] 특정한 최단 경로 - Python

https://www.acmicpc.net/problem/1504 처음엔 함수 없이 1 -> N 까지 다익스트라로 최단경로를 찾고, 그 과정에서 경유지 두개가 포함되는 경우에만  result 갱신하는 방법으로 풀려고 했다.근데 경유지 안지나가고 최단경로를 찾았을 때 다른 경로를 찾지 않아서 코드 완성 못하고 끝냈다.그래서 경유지를 사이에 끼워서 1 -> 경유지1 -> 경유지2 -> N / 1 -> 경유지2 -> 경유지1 -> N 이 두가지 경우를 따로따로 구하고 더 작은 값을 출력하도록 했다. # 성공 코드from heapq import heappush, heappopN, E = map(int, input().split()) # 정점 수, 간선 수adjl = [[] for _ in range(N+1)]f..

algorithm/Dijkstra 2025.02.15

[백준11909/골드5] 배열 탈출 - Python

https://www.acmicpc.net/problem/11909  처음에 문제만 보고 그냥 다익스트라로 푸는 문제인줄알았는데 계속 시간초과났다. 1. (0, 0)부터 시작 -> 이미 더 빠르게 지나온 기록이 있으면 continue2. 현재 칸이 다음 칸보다 작으면 버튼 올려서 칸 맞춰주기3. 최솟값 갱신 # 실패 코드# 다익스트라 - 시간초과from heapq import heappop, heappush# 1. A[a][b] > A[c][d]# 2. 1 visited[r][c]: continue for di, dj in [(1, 0), (0, 1)]: nr, nc = r + di, c + dj if not (0 arr[nr][nc]: ..

algorithm/DP 2025.01.26