시나위

https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 플로이드 와샬 알고리즘을 사용해서 풀면된다. 뒤집지 않고 갈수 있으면 0을 넣고 한번이라도 뒤집어야한다면 1을 넣어서 초기화한다. 이후 floyd-warshall 알고리즘(i에서 k를 거쳐 j를 가능 방법)을 사용해서 최솟값으로 갱신하면 된다. import sys; input = sys.stdin.readline def floyd_warshall(n, visit): for k in range(1..

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 처음 풀어보는 플로이드 와샬 문제이다. 플로이드 와샬을 몰랐기 때문에 다익스트라로 먼저 접근했다. 알고리즘 순서는 다음과 같다. 한 도시를 시작으로 다른 도시까지의 거리를 탐색한다. 모든 도시를 다 탐색해야하기때문에 반복문으로 돌리고 값을 받아온다. 한도시에서 다른 도시까지의 거리를 바탕으로 사이클을 탐색한다. 도시 사이 거리는 단방향이므로 양방을 모두 더해줘서 ..