thisisuser's study

마지막으로, UI를 개선하고 데이터 저장 및 불러오기 기능을 제작하였다. 먼저 UI 개선이다. 기존에 제작한 프로그램에서는 유량이 어느 방향으로 흐르는 지 알 수 없었다. 따라서 방향을 표시해주어 이를 알 수 있도록 제작하였다. 화살표는 밑변 16, 높이 14의 이등변삼각형으로 구성해 주었다. 이때, 유량이 흐르는 방향을 판별하여 이를 향하게 해주어야 하므로 삼각비를 응용하였다. 기본적으로 다음과 같이 설정을 해줄 수 있다. 꼭짓점에서 20만큼 뺀 이유는 정점의 반지름이 20으로 표현되기 때문에 이렇게 설정하였다. 각도는 기울기로 구현하였고, 이 과정에서 고려해야 할 사항이 2가지 존재한다. 1. 기울기가 x축에 수직일 때 두 정점을 지나는 직선의 기울기는 $\frac{y_{to} - y_{from}}{..

이번에는 생성한 그래프에서 두 정점 간의 최대 유량을 계산하는 알고리즘을 구현하였다. 최대 유량 문제란, 용량이 주어진 간선에 대해 최대 유량을 구하는 문제를 의미한다. 다음과 같이 그래프가 주어진 상황을 가정하면, 1 → 3 → 4 → 2로 1의 유량을 흘려주고, 1 → 4 → 2로 2의 유량을 흘려주고, 1 → 3 → 2로 2의 유량을 흘려주면 총 5의 유량을 보낼 수 있다. 최대 유량 알고리즘으로는 에드몬드-카프 (Edmonds-Karp) 알고리즘을 사용하였다. 시간복잡도는 $O(VE^{2})$으로, 돌아가기에는 충분한 알고리즘이기에 이를 활용하였다. 두 지점을 연결하는 어떠한 경로에 대해 유량을 흘려줄 수 있다면, 항상 흘려주는 것이 더 이득이다. 즉, 그리디하게 문제를 해결할 수 있다. 만약 이..

이번 시간에는 그래프를 생성 및 수정할 수 있는 프로그램을 제작하기로 했다. 먼저 다음과 같이, 그래프를 다룰 수 있는 변수들을 설정했다. //network flow int [][]capacity = new int[101][101]; int [][]flow = new int[101][101]; int []parent = new int[101]; //graph simulation float []x = new float[101]; float []y = new float[101]; boolean []exist = new boolean[101]; 먼저 capacity와 flow는 각각 해당 간선의 용량과 현재 흐르고 있는 유량을 의미한다. 네트워크 플로우 알고리즘을 사용할 것이기 때문에 이렇게 2개의 데이터를 ..