문제

역사

풀이

다른분들 풀이 보면 dfs, bfs로도 풀린다고 한다.

보통 플로이드 와샬로 많이 풀고 있는데, 이 알고리즘 또한 최소 비용 알고리즘으로 사이클이 없는 모든 edge에서 최소 비용인 알고리즘을 찾는 방식이다.

이전에 크루스칼에서 최소 비용을 찾을때 모든 간선의 비용중 가장 작은 것부터 사이클이 없는지 확인 한 후 확인 하였지만
플로이드 와샬은 모든 간선에서의 최소 비용을 찾는 방식이라고 한다. 문제만 보면 플로이드 와샬인지 잘 몰랐으나, 문제 자체에서 사이클이 없다는 것을 간접적으로 보여준다. 시간 순서대로 전후 관계가 뚜렷한 그래프가 발생되기 때문이다.

1다음 2가 온다고 할때 1을 a 2를 b로 작성하고 이것을 2차원 배열에 순서를 배열할 수 있는데, 다음과 같이 나타낸다

map[a][b] = -1;
map[b][a] = 1;

map[a][b] = -1 는 a 다음으로 b가 일어 났다는 뜻이다.
만약 a와 b사이에 k라는 숫자가 있다고 한다면 다음과 같이 나타낸다.

map[a][k] = -1;
map[k][b] = -1;
map[k][a] = 1; // k다음 a가 시간순서대로 위치할 수 없음
map[b][k] = 1; // b다음 k가 시간 순서대로 위치할 수 없음

만약 k가 중간에 위치한 숫자가 맞다면 map[a][k] = -1, map[k][b] = -1 이고 시간 순서대로 위치 한 것이 맞을 것이다.

이 k라는 숫자는 edge를 순서대로 방문하기 위해 1 부터 N까지 계산할 것이다.

for (int k = 0 ; k <= n; k++) {
	for (int i = 0; i <= n; i++) {
    	for (int j = 0; j <= n; j++) {
    		if (map[i][j] == 0) {
            	// 시간 순서대로 들어온 것이 맞다
            	if (map[i][k] == -1 && map[k][j] == -1) {
                	map[i][j] = -1;
                // 시간 순서대로 들어온 것이 아님
                } else if (map[i][k] == 1 && map[k][j] == 1) {
                	map[i][j] = 1;
                }
            }
    	}
    }
}

모든 간선을 방문 하면서 최소 값을 갱신 해주는 플로이드 와샬 알고리즘의 내용이 들어간 가장 중요한 부분이다.
여기는 값을 갱신해주는 대신 간선이 순 방향으로 들어갔는지만 갱신 해주면 되었던 알고리즘이었다.

어렵슴.. 연습하자.

전체 코드

전체 코드