2848 - 고창어

https://www.acmicpc.net/problem/2848

그냥 쭉 쓰다보니 코드가 너무 길어졌다.
새로 정의한 사전순 문자열로부터 문자의 순서를 재정의한다.
예제 같은 경우는 l->u, l->k, u->k, k->a 이렇게 4개

1. 올바른 순서가 없는 경우
 : 모순이 존재한다는 것. 싸이클이 있다는 것이다.
 : 플로이드 돌린 후에 다시 자신으로 돌아오는 경로가 있으면 싸이클임.

2. 가능한 순서가 여러개인 경우
 : 사전의 첫 글자가 여러개이거나, (첫 글자로부터) k번째 숫자에 올 수 있는 수가 여러개인 경우.

위에 적은 것만 구현했는데 코드가 1.6KB나 된다. 소스 정말 더럽다.

11581 - 구호물자

https://www.acmicpc.net/problem/11581

2015 인하대학교 프로그래밍 경시대회 G번

처음에는 BFS를 돌면서 다시 방문하는 정점이 있는 경우 NO CYCLE을 출력하고 끝내려했는데, 코딩 미스인건지 오답을 맞았다. (이거 BFS로는 안되는건가요? 누가 댓글로 답변 바람) (참고로 다들 DFS로 푼 것 같다..)

딱히 좋은 아이디어는 안 떠올라서 플로이드 와샬로 정점과 정점이 이동 가능한지 저장했다. 그리고 1번 정점에서 $i$번 정점까지 방문 가능한 것들 중에 $i$번 정점에서 $i$번 정점으로 다시 돌아올 수 있는 (싸이클이 생기는) 경우가 있다면 CYCLE을 출력하도록 했다.

입출력 몇 개를 예로 적어놔야겠다.

예제 #1

6
2 2 3
2 4 6
1 4
1 5
1 3

CYCLE

예제 #2

6
2 2 6
1 6
1 4
2 2 5
1 3

NO CYCLE

1613 - 역사

https://www.acmicpc.net/problem/1613

입력으로 주어지는 사건들의 관계를 방향그래프로 생각하면 사건 A와 사건 C 사이에 A->B->C 의 순서가 되는 사건 B가 있으면, 사건 C는 사건 A 이후에 발생했다는 사실을 알 수 있다.

플로이드 와샬을 통해 각 사건들의 관계를 모두 구하면 s줄에 걸친 물음에 대답할 수 있다.

2660 - 회장 뽑기

https://www.acmicpc.net/problem/2660

친구의 친구 사이는 친구이므로, 각 사람들에 대해 서로 가장 가까운 정도를 구할 수 있다.

구해진 가까운 정도(최단 경로)들이 가장 작은 사람들의 리스트를 만들어 출력한다.

1507 - 궁금한 민호

https://www.acmicpc.net/problem/1507

(연결된 정점을 x-x 로 표현하겠다)
i-j-k 가 가능한 i-k 가 있다면 i-k 인 간선은 필요가 없다. 왜냐하면 i-k 는 i-j, j-k 로 표현이 가능하고, 같은 거리로 더 많은 도시를 갈 수 있도록 유지되기 때문이다.
결과적으로 필요한 간선만 남게 된다.

불가능한 경우는 잘못된 입력이 주어지는 경우이다. 이를테면 주어진 입력으로 a->b->c 를 해보면 a->c 보다 더 작게 나온다던가 그런 입력.

6156 - Cow Contest

https://www.acmicpc.net/problem/6156

처음에는 위상정렬인가 생각했다. 위상정렬로 어떻게 하지 생각하다가 필요없단 걸 깨달았다.
한 소가 나머지 소들과 한번씩 붙어봤다면 (모두를 알면) 자신의 순위를 알 수 있다.

소를 하나의 정점으로 생각하면 어떤 한 정점과 연결된 선의 갯수가 V-1(자신을 제외한 나머지)개 라면 순위를 알 수 있다.

들어오는 간선(indegree) + 나가는 간선(outdegree) = V-1 (문제에선 N-1) 이면 된다. 정점끼리 서로 연결되었는 지는 방향 그래프를 유지해야하고, 셀 때만 구분없이 세면 된다.

7 6
4 3
3 2
1 2
2 5
5 6
5 7

는 2번 소, 5번 소 = 2개 가 나와야 한다.

1389 - 케빈 베이컨의 6단계 법칙

https://www.acmicpc.net/problem/1389

무방향 그래프에서 모든 정점이 서로 얼마만큼 가까운지(최단경로)를 계산하는 문제이다.

모든 정점에 대해 각각 최단경로를 구해도 되지만,(다익스트라라면 $O(V(E+VlogV))$) 문제에서 조건이 2 ≤ N ≤ 100 이므로 플로이드 와샬 알고리즘$O(V^3)$을 사용해도 충분하고 소스가 깔끔하다.

소스 첨부

3075 - Astromeeting

미팅하는 사람들이 어떤 은하 k로 가는 비용이 최소가 되는 은하 k를 찾는 문제이다.
그러기 위해선 모든 정점 간의 최단 거리를 구해야하므로, 플로이드 와샬 알고리즘을 썼다.

이제 모든 정점 간의 최단 거리는 구해졌고, (한 정점 K 에서 미팅을 하는 사람의 은하 i)들의 각 비용의 합이 최소가 되는 순간 미팅 장소 은하 K를 갱신했다.