프로그래민👨‍💻

플로이드 와샬을 활요하는 문제였다. 이 문제같은 경우 잘생각할 필요가 있는 문제이다. 이미 주어지는 입력이 최소 이동 시간이고, 여기서 구해야할 것이 필요없는 도로를 골라내는 문제이다. 즉 입력을 이용하여 다시 플로이드와샬을 돌면서 map[i][j] = map[i][k] + map[k][j] 인 경우 map[i][j] 경로가 필요없게 됨으로 이것을 찾아주었다. 또한 불가능한 경우는 최소값을 갱신할 수 있을경우이기에 이것에 대한 처리도 같이 해주었다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 ..

플로이드와샬과 DFS를 같이 활용하는 문제이다. 내용자체를 이해하는데 좀 어려웠던 문제였다. 이 문제에서 결론적으로 구하는 것은 1. 서로 연결되어 있는 노드 중에서 2. 다른 노드로의 최대거리가 가장 작은 노드를 대표로 선정 하는 문제이다. 이러한 과정에서 1번을 해결하는 데에 DFS, 2번을 해결하는데 N값이 100이하이기에 플로이드와샬을 사용하였다. 전체적인 로직을 정리하자면 다음과 같다. N이 100이하이기에 플로이드와샬을 이용하여 전체 노드의 최단 경로를 map[][] 에 저장 1~N까지의 노드를 각각 확인하여 다른 노드로의 최대값을 maxDistanceToOther에 저장 그 후 1~N까지의 노드중 방문안한 노드에 대해 graph를 이용하여 DFS DFS를 돌면서 maxDistanceToOth..

플로이드와샬을 활용하는 문제였다. 기존 플로이드와샬 문제와는 접근법을 다르게해야 풀 수 있는 문제였다. 이 문제 같은 경우는 단방향에서 양방향으로 바꿔야하는 길의 수, 즉 단방향으로 연결되어 있는 곳에 반대 반향의 길을 연결해야하는 갯수를 체크해야하는 문제이다. 이 문제 같은 경우는 N의 최대값이 250이기에 최단거리를 구하는 플로이드와샬 기법을 활용할 수 있다. 다만, 기존의 플로이드와샬 문제와는 다르게 경로의 비용 선정에 있어서 조금 다른 부분이 필요하다. 즉, 구해야하는 것이 단방향에서 반대방향의 갯수이기에 단방향이 입력으로 들어왔을 때 반대방향에 대해서 1, 그외에는 0으로 설정해주는 것이 필요하다. 다시말해 기존 경로에 대해서는 0, 새로 생성할(단뱡향에서의 반대방향)경로에 대해서는 1로 설정을..

최소 비용을 구하는 문제이다. 이 문제의 경우엔 최대 n이 100이하이고 출력시 모든 점에서 모든 점에 대한 최소비용을 출력해야함으로 가장 간단히 구현할 수 있는 플로이드와샬 알고리즘을 사용하면 된다. 플로이드와샬은 3중 for문을 이용한 알고리즘으로 만일 한점을 거친 거리가 더 가깝다면 갱신을 해주는 식으로 모든 정정들을 확인하는 알고리즘이다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package boj2; import java.io...

DFS를 이용하여 푸는 문제이다. 유향 그래프이기때문에 하나의 정점을 기준으로 1.정방향 DFS, 2.역뱡항 DFS 둘다를 거쳤을 때 모든 정점을 방문한형태를 나타낸다면 자신의 위치를 알고있는 정점으로 간주할수 있게되는 성질을 이용하여 풀었다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 package boj2; import java.io.B..