프로그래민👨‍💻

다익스트라를 활용한 문제였다. 총 2번의 다익스트라를 활용하였는데, 출발점 기준 그리고 친구 기준으로 두번 다익스트라를 활용하였다. 출발에서 목적지까지의 거리랑 출발에서 친구 + 친구에서 목적지 까지의 거리를 비교하는 간단한 문제였다. 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 81 82 83 84 85 86 87 88 89 90 91 92..

플로이드 와샬을 활요하는 문제였다. 이 문제같은 경우 잘생각할 필요가 있는 문제이다. 이미 주어지는 입력이 최소 이동 시간이고, 여기서 구해야할 것이 필요없는 도로를 골라내는 문제이다. 즉 입력을 이용하여 다시 플로이드와샬을 돌면서 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의 최대값이 1000이기에 플로이드와샬 기법보다는 다익스트라가 적합할 것 같아서 다익스트라로 접근하였다. 이 문제는 경로가 주어지고 특정 목적지를 왕복하는 문제였다. 따라서 두가지로 나누어 풀어보았다. 첫번째로 시작점에서 목적지까지의 다익스트라, 두번째로 목적지에서 시작점까지의 다익스트라, 이 두가지를 구하여 시작점을 바꿔가며 최대값을 확인하여 답을 풀었다. 즉 max(distanceFromStart[end] + distanceFromEnd[start]) 값을 구하였다. 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..

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

두번의 BFS를 이용하였다. 첫번째 BFS로 각 섬마다 번호를 지정해주었고, isEdge라른 함수를 이용하여 현재 위치가 가장 자리인 것이 확인이 되면 두번째 BFS를 사용하여 다른 섬까지의 거리를 구해주는 방식으로 해결하였다. 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 81 82 83 84 85 86 87 88 89 90 91 92 93 ..

BFS를 사용하는 문제이다. 다른 숨바꼭질 시리즈와 다르게 몇가지 경로로 목적지에 도달할 수 있냐를 체크해야 함으로 visit 체크를 queue에 offer할 때가 아니라 queue에 poll 할때 체크해주었다. 또한, 처음 도달한 경우가 최솟값이므로 그 값을 이용하는 과정을 거쳤다. 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..

BFS를 사용하여 최단 시간을 찾는 문제이다. 단, 일반적인 BFS와는 다르게 움직일때 두가지(일반, 말) 방법으로 움직이게 되고, 말처럼 움직이는 경우는 횟수가 제한이된다. 따라서 visit 배열을 3차원으로 visit[행][열][말처럼 움직일수 있는 남은 횟수] 로 만들어서, 구한다. 그리고 queue에서 poll 할때 도착지점인 경우 result와의 최솟값을 비교해주어서 답을 구한다. 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 6..

BFS를 사용하여 최단 시간을 찾는 문제이다. 이 문제는 일반 BFS와 다르게 풀어야 한다. 일반적인 BFS를 하기 위해선 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하다. 그러나 이문제는 가중치가 0이 존재하므로 단순한 BFS를 사용할 수 없고, 다음과 같은 방법으로 풀수 있다. - 다익스트라 알고리즘 : 모든 간선이 다를 경우 사용하기 용이 - 0-1 BFS : 가중치가 0인 간선에 연결된 정점은 큐의 맨뒤가 아닌 맨앞에 넣는 방법 - *2 를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법 이 문제에선 간선이 0, 1 두가지 종류여서 다익스트라 알고리즘 보단 Deque을 이용하여 가중치가 0일 때, Deque의 addFirst..