꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1613 전형적인 플로이드-와샬 알고리즘을 사용하는 문제였습니다.입력을 받을 때 history[일찍 발생한 사건][늦게 발생한 사건] = -1 로 초기화 하고 history[늦게 발생한 사건][일찍 발생한 사건] = 1로 초기화합니다.그리고 플로이드-와샬 알고리즘을 적용하면 간단하게 풀리는 문제였습니다. #include using namespace std; const int MAX = 400 + 1; int N, K; int history[MAX][MAX]; //전형적인 플로이드 void floyd(void) { for(int k=1; k> K; for (int i = 0; i < K; i++) { int first, second..

문제 링크입니다: https://www.acmicpc.net/problem/1389 플로이드-와샬 알고리즘을 사용하여 푸는 문제였습니다.최소 베이컨 수를 구해야하기 때문에,1. i와 j가 아직 모르는 경우 k를 통해 아는 경우 단계 수를 업데이트하고2. i와 j가 서로 알더라도 k를 통해 알면 단계 수가 줄어들 경우에도 업데이트합니다. 이후에는 각 사람마다 베이컨 수를 계산하고 동등한 베이컨 수더라도 인덱스가 적은 사람을 출력하라고 했기 때문에 result>sum일 때만 업데이트해주면 됩니다! #include #include using namespace std; const int INF = 987654321; const int MAX = 100 + 1; int N, M; int graph[MAX][MAX..

문제 링크입니다: https://www.acmicpc.net/problem/11403 플로이드-와샬 알고리즘을 적용하여 푸는 문제였습니다.여태까지 풀었던 플로이드 알고리즘 문제와는 달리 자기 자신한테도 가는 경우도 고려하는 것이 핵심이였습니다! #include using namespace std; const int MAX = 100; int N; int graph[MAX][MAX]; void floyd(void) { //i->j로 가는 길이 없어도 //k를 거쳐갈 수 있으면 갈 수 있다고 여긴다 for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (graph[i][k] && graph[k][j]) gr..

문제 링크입니다: https://www.acmicpc.net/problem/11404 플로이드 알고리즘을 사용하면 쉽게 풀리는 문제였습니다.정식 명칭이 플로이드-와샬 알고리즘인 것은 오늘 처음 알았네요. 간단하게 플로이드 알고리즘을 설명하자면 from에서 to로 곧장 가는 것보다 via를 통해 가는 것이 더 빠를 경우를 찾는 알고리즘입니다.코드를 보면 쉽게 이해할 수 있을 것입니다!(실행속도 향상을 위해 중간 중간 continue문을 넣었습니다.) #include #include using namespace std; const int MAX = 100 + 1; const int INF = 100000 + 1; int N, M; int graph[MAX][MAX]; void floyd(void) { //v..