프로그래민👨‍💻

위상정렬을 이용한 문제였다. 이 문제는 그림에 주어졌듯이 건물사이의 우선순위가 존재하고 사이클이 생기지 않기때문에 위상정렬을 사용하여 접근하였다. 다만 주의할점은 건설함에 있어 이전것이 다 지어져야하는 시간을 가져가야하기 때문에 시간을 갱신함에 있어 max 값을 처리해주는 것을 생각해야한다. 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 ..

위상정렬을 이용한 그래프 문제였다. 이 문제는 부품사이의 순위가 존재하고 서로 이어보면 DAG를 형성할 수 있기에 위상정렬을 사용해보았다. 큰부품 -> 작음부품이렇게 바라보도록 그래프를 그리고, 갯수만큼 곱해주면서 위상정렬을 돌면 최소부품이 몇개 필요한지 찾을 수 있는 간단한 문제였다. 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 ..

위상정렬을 이용하여 풀었던 그래프문제이다. 이 문제를 맨처음 접했을 때 각 노드끼리의 순위가 존재하고 싸이클이 없기에 위상정렬을 사용해보았다. 맨처음 문제를 접근을 다음과 같이해보았다. 만일 1등, 2등, 3등, 4등이 존재한다면 4등->3등, 3등->2등, 2등->1등 이런식으로 그래프를 그려보았다. 하지만 이 문제는 순위가 뒤바뀌는 경우가 있는데 맨처음 내가 적용한 방식은 순위가 뒤바뀌는 것을 처리해주지 못하기에 그래프를 새롭게 그려보았다. 즉, 4등->3등, 4등->2등, 4등->1등, 3등->2등, 3등->2등, 2등->1등과 같이 순위가 낮은것이 자기보다 높은 순위를 모두 볼수 있도록 그래프를 그리는 방식을 수정하였다. 이런 방식을 통해 순위가 바뀌는 경우도 처리해주었고, 그래프를 새로그린다음에..

위상정렬을 이용하여 풀은 문제였다. 문제를 맨처음 파악했을때, 일의 우선순위가 있고, 일끼리 싸이클을 만들지 않는 DAG임을 보장받을 수 있는 조건이라 위상정렬을 사용하여 문제를 풀었다. 이 문제에선 우선순위가 높은것 -> 우선순위가 낮은것 으로 간선을 연결해 주었고, indegree배열과 queue를 이용하여 위상정렬을 구현하였다. 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 ..

그래프의 사이클을 찾는 문제이다. DFS를 이용하여 그래프의 사이클을 찾아서 pq에 저장하였다. DFS를 이용하여 그래프의 cycle을 찾을때는 visit 배열 뿐만 아니라 finished 배열을 하나 더 사용해준다. finished를 이용하여 이미 완전히 탐색이 끝났는지를 확인해주었다. DFS를 도는중 만일 visit가 true이지만 finished가 false 인곳을 찾는다면 cycle을 찾은 조건을 만족한다. 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..

그래프의 BFS문제이다. List의 배열을 이용한 간단한 그래프 BFS 문제였다. 촌수를 구하기 위해 visit배열을 -1로 초기화 시켰고 start부터 시작하여 end가 만날때까지 실행을 시켰다. 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 package study4; import java.io.BufferedReader; import java.io.InputStreamReader; impor..

인접리스트의 DFS로 풀수있었던 문제이다. 리프노드에서 리프노드까지 가는 가장 긴경우를 지름이라 할 수 있는데 그것을 찾는 문제였다. 맨처음엔 가장 긴 간선을 기준으로 찾아보는 방법을 시도했는데, 가장 긴 간선이 꼭 포함되라는 보장이 없으므로 틀린방법으로 접근하였었다. 도움을 받아 풀었는데 다음과 같은 방법으로 풀었다. 1.루트에서 가장 멀리있는 리프노드의 인덱스를 찾고, 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 4..

모든 정점을 N-1개로 연결하는 MST 문제이다. MST를 해결하기 위해선 간선기준인 Kruskal 알고리즘과 정점기준인 Prim 알고리즘을 사용할 수 있다. 두 문제는 어쨋든 출발점, 도착점 비용을 알아야하기 때문에 문제에서 비용을 구하는 방법을 생각해보았다. N이 최대 100,000임으로 2중for문은 사용불가하여 고민해본 결과, 전체 정점을 x,y,z로 각 각 정렬했을때 하나 뒤의 정점과의 x,y,z 차이를 이용하여 간선을 구하는 방법을 고안하였다. 이렇게 모든 간선들의 비용을 PriorityQueue에 저장한다음 UnionFind를 이용하여 MST를 구하였다. 그래프의 간선들을 만듬에 있어 충분한 고민이 필요했던 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

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..

이 문제는 위상정렬(Topoologicl Sort)를 이용하는 문제이다. 위상정렬을 이용하기 위해선 DAG(Directed Acyclic Graph, 유향 싸이클없는 그래프)를 만족해야지 사용할 수 있다. 위상정렬이란 DAG의 정점들을 쭉 나열하였을 때 왼쪽에서 오른쪽(한바향)으로만 모든 간선이 이동하는 모양을 가지도록 정렬되게 하는 알고리즘이다. 즉 다음과 같은 모양으로 모든 정점이 정렬되는 것이다. 이러한 위상정렬을 하기위해선 우선적으로 싸이클이 없는 DAG임을 확인하고, 그다음 indegree배열을 사용하여 자신으로 들어오게 되는 간선의 수를 저장한다. 그 후 queue를 이용하여 indegree[index]=0이 되면 queue에 offer해주고 인접리스트를 돌면서 indegree들을 하나씩 줄여..