일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
- 도커
- Docker-compose
- 너비 우선 탐색
- 13549
- 서버리스
- 프로그래머스
- 코딩테스트
- 모각코
- k8s
- docker
- kubernetes
- BaaS
- kubernets
- 백준
- cloud
- 타원곡선
- golang
- sia
- observability
- 비트코인
- Props
- 설치과정
- Jenkins
- ChangeCipherSpec
- Vue
- Programmers
- 숨바꼭질3
- alert
- vue.js
- FAAS
- Today
- Total
작업공간
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번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
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번: 최종 순위
올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에
www.acmicpc.net
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]++;
}
}
}
'2020 동계 코독하구만' 카테고리의 다른 글
6th Meet - 코독하구만 (0) | 2021.01.27 |
---|---|
4th Meet - 코독하구만 (0) | 2021.01.13 |
3rd Meet - 코독하구만 (0) | 2021.01.05 |
2nd Meet - 코독하구만 (0) | 2020.12.30 |
1st Meet - 코독하구만 (0) | 2020.12.23 |