플로이드 워셜4 [Python][백준 1719] 등산 https://www.acmicpc.net/problem/1486 1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 입력된 알파벳을 숫자로 변환 (ASCII 코드 응용) 2. 변환한 높이정보를 활용해 상하좌우 오버플로 체크 후 해당 위치까지 가는데 걸리는 시간 계산 2.1 높이가 출발 위치보다 높으면 둘의 차의 제곱 2.2 출발 위치보다 낮으면 1 2.3 행렬 형태로 저장된 값을 리스트 형태로 변형 i*(가로열 길이) + j 3. 얻은 값으로 플로이드 워셜.. 2024. 3. 28. [Python][백준 1719] 택배 https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 플로이드 워셜을 통해 최단거리를 계산한다 2. 최단거리 계산을 위해 비교하며 가장 먼저 거쳐간 집하장을 저장한다. 3. 저장된 집하장 정보가 없다면 현재의 k값을 있다면 원래의 집하장 정보를 저장한다. */ import sys input = sys.stdin.readline INF = float('inf') def floyd_warshall(graph): n = le.. 2024. 3. 26. [Python][백준 1956] 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 일방통행 (양방통행 X) 2. 거리의 합이 가장 작은 사이클을 찾아야 하며, 없으면 -1 출력 3. 플로이드 워셜을 통해 최단 거리를 계산할때 사이클이 있어야 하므로 스스로를 0으로 초기화 하지 않음 4. 나온 결과물 중 INF가 아닌 가장 작은 값을 출력 사이클 만드는 접근법만 생각해내면 간단한 응용이었다. */ impor.. 2024. 3. 26. [Python][백준 21278] 호석이 두 마리 치킨 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 플로이드 워셜을 통해 각 건물간의 거리를 구한다. 2. 치킨집은 총 두개이고 각 치킨집에서 다른 건물까지 걸리는 시간을 비교한다 3. 더 작은 값의 2를 곱한뒤 저장한다 (왕복 소요 시간) 4. 각 치킨집의 위치를 완전탐색으로 돌리며 위의 방법으로 구한 값을 비교한다. 5. 더 작은 값의 치킨집 위치를 같이 저장한다. 플로이드 .. 2024. 3. 23. 이전 1 다음