Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처여행 가자 골드 4 📖 문제 서로소 집합 또는 BFS-DFS 알고리즘 둘중 하나로 풀 수 있는 문제다. 주어진 섬들을 여행 시작점을 출발로 탐색해서여행 계획 섬들을 전부 방문했는지만 따지면된다.  서로소 집합의 경우 여행 계획 섬들의 부모가 모두 같으면 여행 가능하다. 🔅 문제 풀이 [BFS]import java.io.*;import java.util.*;public class Main { static boolean[] visited; static boolean[][] graph; // 방문한 곳을 여행 계획에서 체크하면 된다. // 여행계획 섬을 방문하지 않았다면 이는 불가능한 것 public static void main(String[] args..

🧫 문제 분석 ✔️ 출처중량제한 골드 3 📖 문제 최단 경로 + 최대신장(최소 신장의 반대라서 이렇게 붙였다) + 이분탐색 문제다.근데 본인은 최대 신장 트리로 안풀고, 현재 이분탐색 문제를 공부중이므로 이분탐색 + BFS 최단경로로 풀었다.  이분탐색으로 찾고자 하는 것은 두 섬 사이의 경로 이동 비용 최댓값이다. 가장 비용이 큰 값을 max로 잡고 1 ~ max 사이를 이분탐색하면서 mid값으로 BFS 탐색을 한다. BFS 탐색에서는 공장이 있는 섬A에서부터 탐색을 하되 mid 값 (중량)을 다리의 중량제한이 버틸 수 있다면 다음 다리로 탐색한다. 공장이 있는 섬 B에 도착하면 현재 mid 값의 중량은 버틴다는 의미이므로 true를 반환해 알린다.이분탐색에서는 BFS 결과가 true이면 mid 값..

🧫 문제 분석✔️ 출처섬 연결하기 level 3📖 문제 다익스트라로 했다가 생각해보니 이건 최단경로가 아닌 최소비용으로 연결하는 거였다.알고리즘 시간때 배웠던 걸로 기억하는데 최소신장트리 였던걸로 기억한다.  서로소 집합, 유니온, find 등 같은 걸 배웠었는데 기억이 안나서 결국 찾아봤다. https://sskl660.tistory.com/72 자세한 이론은 위 블로그 참조 핵심은 최소 비용으로 정렬하고 연결하는 두 노드(섬)의 부모가 서로 달라야한다. (사이클 방지, 최소 신장 '트리' 이기에 사이클은 없어야한다. )이때 find 메서드를 사용해서 각각 부모를 찾는다. 두 노드의 부모가 서로 다르다면 union 메서드를 사용해서 두 노드 중 부모가 더 작은 곳으로 편입된다. 이때 실제 원소가 편..