HwangHub

문제 링크 문제 해석 트리 구조에서 공통된 조상 중 가장 가까운 조상을 찾는 건 그래프 알고리즘 중 유니온파인드 알고리즘의 '파인드' 부분을 활용하면 될 것으로 보았다. 아울러 그 노드 기준으로 자식 노드의 개수를 세는 건 dfs로 간단하게 구현할 수 있다. 문제 풀이 시간복잡도 : DFS를 인접리스트로 구현하였고(O(V+E)), 파인드 로직에서 최소 공통 root 노드를 찾기 위한 로직에서 트리 높이(h)가 최악의 경우 노드 개수(V)에 근사해지므로 O(V + E)이다. package ssafy.사전학습; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 출발점부터 도착점까지 이동할 때 "최단 거리"를 구해야 함 격자 공간 위에서 이동 조건이 존재 이동할 때마다 가중치(이동 시간)는 기본 1 하지만 소용돌이 구간은 가중치가 달라짐 (시간이 더 오래 걸림) n은 2 이상 15 이하 위 조건을 고려했을 때, 모든 간선의 가중치가 양수이며 최단거리를 구하는 것이므로 다익스트라로 푸는 것을 먼저 고려해봤다. 다만, 아직 다익스트라가 익숙치 않은 탓에 우선순위 큐는 사용하지 않았고, 기본적인 BFS 로직 위에 최단 거리로 각 노드를 갱신하는 로직만 추가하여 구현하였다. 이렇게 할 경우에는 다익스트라의 시간복잡도가..

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