python

문제https://www.acmicpc.net/problem/13168백준 문제집 - 0x1C강 - 플로이드 알고리즘 알고리즘: 구현, 최단 경로, 해시를 사용한 집합과 맵, 플로이드-워셜풀이데이터를 문자열 형태로 저장해야해서 그렇지, 문제 자체는 단순한 플로이드 워셜 문제다.다만 주의해야할 조건이 있다.50% 할인 처리 시, 값이 실수형으로 나올 수 있으므로 미리 처리해줘야함.방법 1: 실수형으로 계산 (/)방법 2: 모든 비용을 2배로 취급 -> 50% 할인 시 정수형으로 처리됨티켓을 중간에 구매할 경우도 따져야 함.시작도시-도착도시 값은 중복으로 주어질 수 있음. 최소비용으로 저장해야함. 즉, 여행 도시가 M개라면 1 ~ M-1 번째에서 티켓을 구매할 경우를 고려해야한다. 실행 순서는 다음과 같다...

문제https://www.acmicpc.net/problem/17182백준 문제집 - 0x1C강 - 플로이드 알고리즘 알고리즘: 브루트포스 알고리즘, 최단 경로, 비트마스킹, 백트래킹, 플로이드-워셜풀이"모든 행성을 탐사하는데" 걸리는 최소 시간을 구해야한다.단, 출발지로 돌아올 필요는 없으며 이미 방문한 행성도 "중복해서" 갈 수 있다. 👆 위 조건때문에 "최소 신장 트리" 문제인 줄 알았으나 결정적인 차이가 있다!한 번 방문한 곳은 따로 비용이 발생하지 않는 최소 신장 트리와 달리, 재방문이 가능하긴 하지만 비용이 발생하는 구조다.따라서 1) 플로이드 워셜로 각 행성간의 최단 경로를 구하고, 2) 방문하지 않은 행성들 중 현재 행성으로부터 소요 시간이 가장 짧은 행성을 선택한다. 참고로 DP(메모이..

문제https://www.acmicpc.net/problem/21940백준 문제집 - 0x1C강 - 플로이드 알고리즘 알고리즘: 그래프 이론, 최단 경로, 플로이드-워셜풀이 플로이드 워셜을 이용해 왕복시간을 계산하는 문제다.문제 설명에 "최대가 최소"라고 되어있는데, 약간 불친절한 설명인듯...준형이와 친구들은 모두 다른 마을에 살고있다.따라서 어떤 마을 A에 대한 왕복시간은 모두 다르다.만약 A 마을의 왕복시간이 [100, 10, 90, 110] 일경우, A 마을에 대한 왕복시간은 110이 된다. (최대)위 과정을 반복해서 1 ~ N 마을의 최대 왕복시간 리스트가 [110, 90, 200, 100, 90]이 되었을때, X가 될 수 있는 마을은 2번, 5번 마을이다. (최소) 참고로 처음 풀이할때는 딕셔..

문제https://www.acmicpc.net/problem/14938백준 문제집 - 0x1C강 - 플로이드 알고리즘 알고리즘: 최단 경로, 데이크스트라, 플로이드-워셜풀이 조건은 한 지역으로 이동 후, 해당 노드로부터 특정 거리 내에 위치한 아이템들만 주울 수 있다는것.따라서 1) 플로이드워셜 수행, 2) 노드를 하나 선택 후, 해당 노드로부터 다른 노드까지의 거리 체크 순서로 진행한다.참고로 자기 지역도 포함이므로, 이동한 지역(노드)의 아이템도 결과값에 더해줘야한다. 전체 코드# 메모리: 33432KB / 시간: 328msfrom sys import stdininput = stdin.readlineINF = float("inf")n, m, r = map(int, input().split())grap..

문제https://www.acmicpc.net/problem/11780백준 문제집 - 0x1C강 - 플로이드 알고리즘 알고리즘: 플로이드-워셜, 역추적풀이 플로이드 워셜을 통해 최단경로(최소비용)를 구하고, 경로를 출력해야하는 문제다.🚨주의해야 할 점은 "시작도시와 도착도시가 같은 경우는 없다." 부분인데, 중복경로가 없다는 게 아니라 "시작도시 != 도착도시"라는 뜻이다.따라서 간선 정보를 입력받을 시 기존 비용과 비교한 뒤 갱신해야한다. 사실 이 문제의 주요 포인트는 역추적이다.플로이드 워셜을 수행 후, a - b의 최단경로는 a - c - d - b 처럼 구성될 가능성이 높다.그러므로 최단경로 갱신 시, a - b의 경로도 갱신해주어야 한다. a - b의 최단경로를 구하는 과정을 예시로 보자.만약..

문제https://www.acmicpc.net/problem/11404백준 문제집 - 0x1C강 - 플로이드 알고리즘 알고리즘: 최단 경로, 플로이드-워셜풀이정말 기초적인 플로이드 워셜 문제다. 플로이드-워셜 알고리즘?최단경로를 구하는데에 사용하는 알고리즘 중 하나다. (+ 다익스트라, 벨만-포드)다른 두 개는 한 정점에서 다른 모든 정점까지의 최단거리를 찾지만, 플로이드 워셜은 모든 정점 쌍 간의 최단경로를 한번에 계산한다. (그리고 음의 가중치도 계산 가능) 원리는 DP와 비슷하다.정점 i에서 정점 j로 가는 경로 중,정점 k를 경유하는 경로가 더 짧다면 👉 최단 경로 갱신for k in range(N): for i in range(N): for j in range(N): ..