HwangHub

해석 이 문제는 인접 리스트를 이용하여 relation group의 개수를 묻는 문제이다. 따라서 그래프 탐색을 통해 연관 노드를 한번에 방문하는 방식으로 로직을 전개하면 마을의 개수를 구할 수 있다. 보통 격자 상에서의 그래프 알고리즘이 아닌, 이 문제와 같이 인접 행렬 또는 인접 리스트를 활용하는 그래프 알고리즘의 시간복잡도는 인접 행렬과 리스트 각각 O(v^2), O(v + e)이다. 이는 아래 구현된 로직에서도 확인할 수 있다. 노드의 개수가 최대 100개라고 주어져 있으므로, 인접 행렬이든 리스트든 관련 없이 문제를 풀 순 있었을 것이다. 간선의 개수는 n(n-1)/2개라고 되어있으므로 인접 행렬로 구현하였다. 풀이 DFS package ssafy.사전학습.그래프; import java.io.B..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 해석 이 문제는 시작 노드와 끝 노드가 정해져 있는 상태에서, 최단 거리를 구하는 문제이므로 기본적으로 BFS를 이용한 그래프 알고리즘 문제일 것이라 가정하였다. 여기서 처음에 문제를 이해할 때에는 가중치가 양수라 생각했기에 다익스트라 알고리즘이 적절할 것이라 보았다. 다익스트라는 시간복잡도가 O(ElogV)이므로 N = 100인 문제에서는 문제 없다. -- 근데 나중에 생각하니, 가중치의 범위에 대한 언급이 없어서 문제가 명확하게 조건을 제시하고 있는 것 같지는 않다. 근데 출제 의도는 다익스트라 였던 것 같다. 다익스트라 알고리즘은 특정 노드를 기준으로, 이와..