프로그래민👨‍💻

인접리스트를 활용한 DFS문제이다. 맨처음 문제접근을 BFS로 하였는데, 이 문제에선 5개의 이어진 노드를 찾는 것이여서 DFS를 활용하여 depth가 5가 될때까지를 찾는게 맞는 방향이라 생각해 DFS로 바꾸어 풀었다. 이 문제에서는 주의할 것은 다양한 방법으로 여러갈래로 찾을 수 있기에 visit[i]=false로 다시 바꾸어 주는 작업이 필수적이다. 이것을 해주지 않아 계속 틀렸었다. 예를 들어 위와 같은 그래프가 있고 1번 정점부터 탐색한다고 생각하자. 첫번째 DFS를 실행시킨 결과가 1-2-4-5-3 이라고 생각한다면 depth는 최대 4까지 밖에 찾지를 못한다. 그렇기에 종료조건을 만족하지 못하고, 재귀가 끝나면서 다시 재귀호출을 하게 된다. 1-2 이상황에서 4를 방문했었기네 1-2-3을 해..

그래프를 사용하여 DFS와 BFS를 하는 기본 문제이다. 그래프를 인접리스트로 구현하여 DFS와 BFS각 각 구현하였다. DFS를 구현할 때는 stack을 사용하는 대신 재귀의 형태로 구현하였다. BFS를 구현할 때에는 queue를 사용하여 구현하였다. DFS에서는 방문할때 바로 visit 체크를 해주었고, BFS에서는 queue에 offer하는 동시에 visit 체크를 해주었다. 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 ..

최단경로를 구하는 문제이다. 이 문제에서 그래프의 가중치가 음을 가지지 않으므로 Dijkstra알고리즘을 사용하여 해결하였다. Dijkstra알고리즘은 Prim알고리즘 기법과 동일하지만 단한가지 차이점을 가진다. 그차이점은 단순 d값의 비교가 아니라 d[dest]와 weight+d[start]를 해주는 것이다. 즉, 단순거리가 아니라 누적거리를 비교해준다. 이렇게 되면 d배열에는 출발점에서 각 index까지의 최단 거리가 저장이 된다. 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..

최소신장트리를 찾는 MST문제이다. 이문제를 해결함에 있어 간선중심의 Kruskal 알고리즘 대신, PriorityQueue를 활용한 Prim 알고리즘을 사용하였다. Edge라는 클래스를 만들어서 weight를 기준으로 빠른 값이 올수있게 최소힙을 사용하는 PriorityQueue를 사용하였다. 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 8..

MST 문제이다. 이 문제를 풀기 위해선 Kruskal 이나 Prim을 사용해야한다. 참고 이 문제를 두가지방법 모두 사용하여 풀어보았다. 첫번째로 Kruskal 알고리즘을 사용하였는데 , 정렬을 함에 있어 PriorityQueue를 사용하였고, 같은 팀임을 보기 위해 UnionFind를 같이 사용하였다. 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 7..

최소신장트리 즉, MST를 구하는 문제이다. 최소신장트리란 , 그래프에서 V개의 접점과 E개의 간선이 있을 때, V-1개의 간선으로 이루어진 트리로 싸이클이 생겨나지 않고, 방향이 없으며 간선들의 합이 최소일 때를 말한다. 구하는 대표적인 알고리즘으로는 Kruskal, Prim이 있다. ※그래프 정점V 와 간선E로 이루어진 연결관계를 모아 놓은 자료. 프로그래밍상 표현법은 다음과 같다. - 간선의 배열 : 정점과 정점의 연결정보인 간선을 모아놓음 - 인접 리스트 : 각 정점별로 연결된 정점의 정보를 모아놓음(ex. List[]) - 인접행렬 : 2차원 행렬에 각 정점과 정점간의 연결정보를 표시(ex. arr[][]) ※Kruskal 알고리즘 그래프에서 간선을 기준으로 MST를 찾고 싶을 때 사용하는 알고..

그래프를 구현하는 문제였다. 그래프를 구현하기 위해 메모리측면을 고려하여 배열보단 리스트를 사용하였다. 리스트로 그래프를 구성한 후 재귀를 이용한 DFS를 이용하여 모든 정점을 방문하도록 하였다. 방문하는 과정에서 flag를 인자로 주어 두팀으로 나눌 수있도록하였다. 모든 DFS끝난 후 바로 이어서 다시 방문하여서 만일 같은 flag를 가지고 있다면 조건을 만족하지 않는 식으로 구성하였다. 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..