5th Meet - 코독하구만

Daily Object

    -  Floyd-Warshall, Topological Sort 알고리즘을 복습하고 예제를 통해 적용한다.

Review

    -  Floyd-Warshall은 학기 수업 때 시험 비중이 낮아서 중요하게 보지 않았다.

      그래서 이번 모각코에서 복습을 하며 전보다 확실히 체득된 것이 느껴졌다. 

 

    -  Topological Sort는 학기 수업 때 과제로도 수행했었던 알고리즘이라 개념 숙지는

      따로 필요없었지만 문제가 난이도가 있어 시간이 오래걸렸다. 타인의 코드를 참고하였다.

 

Floyd-Warshall ( 백준 11404 )

  그래프에서 모든 정점 사이의 최단 거리를 구하기 위한 알고리즘

  다익스트라 알고리즘과는 달리 사이클이 없는 경우 음수 가중치 처리가 가능하다.

  Time Complexity : O ( V ^ 3 ) 

 

Topological Sort ( 백준 3665 )

일의 진행 순서를 구하기 위한 알고리즘

방향그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열함

 

11404번: 플로이드

i = 시작점 k = 경유지점 j = 도착점 으로 잡고,

i~k 과 i~k~j을 비교해서 최단 거리를 갱신한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 플로이드 알고리즘 사용
// 플로이드 문제
// 모든 정점을 출발점으로 하여 모든 정점을 목적지로 했을 때의 최단경로를 구하는 알고리즘
public class Main {
	static int[][] map;
	static final int MAX_VALUE = 10000001;
	
	public static void main(String args[]) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.valueOf(st.nextToken());
			st = new StringTokenizer(br.readLine());
			int m = Integer.valueOf(st.nextToken());
			map = new int[n][n];	// 이제 모든 인덱스에서 -1 해주기

			for(int i = 0; i < n; i++) {
				Arrays.fill(map[i], MAX_VALUE);	
				map[i][i] = 0;
			}
			
			for(int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int start = Integer.valueOf(st.nextToken()) - 1;	// 0부터 시작
				int end = Integer.valueOf(st.nextToken()) - 1;	// 0부터 시작
				int weight = Integer.valueOf(st.nextToken());
				if(map[start][end] > weight) {
					map[start][end] = weight;	
				}
			}
			
			floyd(n);
			StringBuilder sb = new StringBuilder();
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(map[i][j] == MAX_VALUE) {
						map[i][j] = 0;
					}
					sb.append(map[i][j]).append(" ");
				}
				sb.append("\n");
			}
			
			System.out.println(sb.toString());
		}
		catch (NumberFormatException e) {
			System.exit(0);
		}
		catch (IOException e) {
			System.exit(0);
		}
	}
	
	// 플로이드 알고리즘
	public static void floyd(int n) {
		for(int k = 0; k < n; k++) { // 경유 지점 
			for(int i = 0; i < n; i++) { // 출발 지점
				if(k == i) {
					continue;
				}
				for(int j = 0; j < n; j++) { // 도착 지점 
					if(i != j && i != j) {
						if(map[i][j] > map[i][k] + map[k][j]) {
							map[i][j] = map[i][k] + map[k][j];
						}
					}
				}
			}
		}
	}
}

3665번: 최종 순위

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int n;
    static char[][] graph;
    static int[] indegree;
    static final int SUCCEESS = 0;
    static final int IMPOSSIBLE = 1;
    static final int NOT_DETERMINED = 2;
    static Queue<Integer> queue;
    static List<Integer> list;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = Integer.parseInt(sc.next());
        
        while(T-- > 0) {
            // 팀의 개수
            n = Integer.parseInt(sc.next());
            
            // 인덱스를 '1'부터 제어
            graph = new char[n+1][n+1];
            indegree = new int[n+1];
            // 작년 정보를 입력받는다.(순위별로)
            for(int i=1; i<=n; i++) {
                int team = Integer.parseInt(sc.next());
                for(int j=1; j<=n; j++) {
                    if(graph[team][j] == '\u0000') graph[team][j] = 'O';
                    if(graph[j][team] == '\u0000') graph[j][team] = 'X';
                }
                // 자기자신을 순환하지는 않는다.
                graph[team][team] = 'X';
                
                indegree[team] = i-1;
            }
            
            // 바뀐 등수의 개수
            int m = Integer.parseInt(sc.next());
            for(int i=1; i<=m; i++) {
                int x = Integer.parseInt(sc.next());
                int y = Integer.parseInt(sc.next());
                
                changeState(x,y);
            }
            
            queue = new LinkedList<>();
            list = new ArrayList<>();
            
            // 위상 정렬
            int answer = topological_sort();
            
            // 정답 출력
            sayAnswer(answer);
        }
    }
    
    private static void sayAnswer(int answer) {
        if(answer == SUCCEESS) {
            while(!list.isEmpty()) {
                System.out.print(list.remove(0) + " ");
            }
            System.out.println();
        }else if(answer == IMPOSSIBLE) {
            System.out.println("IMPOSSIBLE");
        }else if(answer == NOT_DETERMINED) {
            System.out.println("?");
        }
    }

    private static int topological_sort() {
        // 주어진 정점의 개수만큼 진행한다.
        for(int i=1; i<=n; i++) {
            // 자기자신으로 들어오는 간선의 개수가 0개인 정점을 찾는다.
            if(indegree[i] == 0) {
                queue.add(i);
            }
        }
            
        // 정점의 개수만큼 반복
        for(int i=1; i<=n; i++) {
            //Queue에 저장된 정점이 2개 이상이면 그들간의 우선순위를 알 수 없다.
            if(queue.size() >= 2) {
                return NOT_DETERMINED;
            }else if(queue.size() == 0) {
                // 진행과정에서 사이클이 형성되었다는 것이다.
                return IMPOSSIBLE;
            }
            
            int curNode = queue.poll();
            // 나중에 정상일 때 순위를 출력하기 위해 저장해둔다.
            list.add(curNode);

            // 모든 원소에 대해서 연결된 정점을 확인하다.
            for(int y=1; y<=n; y++) {
                // 간선이 존재한다면 연결을 끊어주고 indegree 개수도 줄여준다.
                if(graph[curNode][y] == 'O') {
                    graph[curNode][y] = 'X';
                    indegree[y]--;
                    // 그 과정에서 자기자신에게 들어오는 간선의 개수가 0개이면 queue에 넣어준다.
                    if(indegree[y] == 0) {
                        queue.add(y);
                    }
                }
            }
        }
        return SUCCEESS;
    }
    private static void changeState(int x, int y) {
        if(graph[x][y] == 'O') {
            graph[x][y] = 'X';
            graph[y][x] = 'O';
            indegree[x]++;
            indegree[y]--;
        }else {
            graph[x][y] = 'O';
            graph[y][x] = 'X';
            indegree[x]--;
            indegree[y]++;
        }
    }
}