오뚝이개발자

문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 나의 풀이 방법은 두 가지가 있다. s -> v1 -> v2 -> n s -> v2 -> v1 -> n 각 경로가 최소가 되는 것을 찾으면 최종경로 또한 최소가 된다. 따라서 s, v1, v2를 시작점으로 해서 다익스트라 알고리즘을 3번 돌린 뒤에 위 두 경로 중 최단거리를 print하면 된다. 코드 # https://www.acmicpc.net/..

문제 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 나의 풀이 플로이드 와샬 알고리즘을 사용해 중간에 k 지점을 통과할 때 비용을..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 생각의 흐름 이전에 포스팅했던 알고스팟과 유사한 문제이다. 차이점은 2가지이다. 시작점과 끝점의 칸 수를 포함하여 계산한다는 점 알고스팟의 경우 칸의 수가 1인 경우와 0인 경우 모두 이동이 가능했지만 본 문제의 경우 1인 경우에만 이동이 가능하다는 점 코드 from queue import PriorityQueue as pq def dijkstra(): heap = pq() heap.put((1, (0, 0))) crush..

문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 생각의 흐름 (0,0)을 시작점으로 보고 (n-1, m-1)칸, 다시말해 우측 맨 하단의 칸을 도착지점으로 보고 최단경로를 찾기 위한 다익스트라 알고리즘을 적용하면 된다. 이 때, 1이 있는 곳으로 이동할 때에는 벽을 부숴야 하기 때문에 가중치가 1인 것으로, 0인 곳은 가중치가 0인 것으로 보면 된다. 어려운 부분은 최..