HwangHub

문제 링크 해석 어제 백준을 풀면서 플로이드워셜을 학습하고, 잊지 않기 위해 개념 문제를 하나 더 풀었다. 여기서는 플로이드워셜 로직을 활용하여 "직 간접적으로 각 정점끼리 연결되어 있는지 여부"를 검사하는 로직을 구성하게끔 유도한다. 단순한 문제였으므로 코드로 대신한다. 코드 package 알고리즘연습.codetree.그래프.플로이드워셜; import java.io.*; import java.util.StringTokenizer; public class CodeTree_행렬로주어진간선 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(..

문제 링크 문제 해석 트리 구조에서 공통된 조상 중 가장 가까운 조상을 찾는 건 그래프 알고리즘 중 유니온파인드 알고리즘의 '파인드' 부분을 활용하면 될 것으로 보았다. 아울러 그 노드 기준으로 자식 노드의 개수를 세는 건 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..

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

유형 파악 이 문제는 2차원 배열 상의 출발지에서 목적지까지 이동시간의 최소를 구하는 문제이면서, 이동간 시간 가중치가 동일하기 때문에 전형적인 BFS 문제라고 이해할 수 있다. 아울러, 몇 개의 점을 선택하여 제거하는 경우를 세야 하므로 이 부분은 백트래킹 로직을 활용하여 풀어내 주었다. 제출 코드 구성했던 로직의 특징은, 여러 경우에서 도착지에 도달하는 시간이 도출될텐데, 그 경우 중 가장 빠른 경우에서의 시간을 구하는 것을 우선순위 큐를 활용하여 도출해줬다는 것과, 제거하려는 벽을 중복으로 선택하지 않기 위해 selected[][] 라는 배열을 운영한 것이다. 개인적으로 헤맨 부분은, 백트래킹을 통해 제거할 벽을 모두 선택했을 때 bfs를 수행하기 위해 관련 변수들을 초기화해줘야 한다는 것이다. 이..