✨ 자바로 푸는 전력난 문제 풀이 📌 문제 개요 “전력난” 문제는 모든 집(노드)을 전깃줄(간선)로 잇되,기존 모든 전선 설치 비용에서 최소한의 유지 비용만 남기기 위한 문제입니다. 즉, 모든 집이 연결되어야 하고최소한의 전기선만 남겨절약 가능한 비용을 구하는 것이 목표입니다. 이 구조는 전형적인 최소 신장 트리(MST) 문제입니다. 💡 예제 입력7 110 1 70 3 51 2 81 3 91 4 72 4 53 4 153 5 64 5 84 6 95 6 110 0 🛠 알고리즘 접근 방식 전체 간선 비용 합계를 구하고크루스칼 알고리즘으로 최소 신장 트리를 구성전체 비용 - MST 비용 = 절약된 전기 요금 ✅ 핵심 아이디어 간선을 비용 순으로 정렬하고,Union-Find(서로소 집합)을 통해 사이..

https://www.acmicpc.net/problem/9328 🔑 자바로 푸는 열쇠 문제 풀이 (백준 9328) 📌 문제 개요 감옥의 평면도가 주어졌을 때, 상하좌우 이동을 통해 가능한 많은 문서(’$’)를 얻는 것이 목표입니다. 벽은 *, 빈 공간은 ., 문은 A~Z, 열쇠는 a~z, 문서는 $열쇠가 있어야 문을 통과할 수 있음열쇠는 한 번 획득하면 해당 종류의 문을 모두 열 수 있음감옥의 외곽 어느 지점에서든 침입 가능 💡 예제 입력15 17*****************.............**$**B*A*P*C**X*Y*.X.*y*x*a*p**$*$**$******************cz 예제 출력3 🧠 알고리즘 접근 방식 이 문제는 BFS(너비 우선 탐색) 을 기반으로 풀..

https://www.acmicpc.net/problem/1774 🌌 자바로 푸는 우주신과의 교감 문제 풀이 📌 문제 개요 백준 1774번 우주신과의 교감 문제는N개의 신들과 이미 연결된 M개의 통로 정보가 주어졌을 때,모든 우주신이 연결되도록 추가로 연결해야 할 최소 거리의 합을 구하는 문제입니다. 각 우주신은 2차원 좌표 위에 존재이미 연결된 통로는 추가 비용 없이 사용 가능목표는 전체 우주신을 연결하는 최소 비용 💡 예제 입력4 11 12 22 43 31 4 예제 출력2.00 🛠 알고리즘 접근 방식 이 문제는 기존 연결 정보를 고려한 최소 신장 트리(MST) 문제입니다. ✅ 핵심 아이디어 크루스칼 알고리즘을 사용해 거리 기준 오름차순 간선 선택M개의 이미 연결된 통로는 먼저 uni..

https://www.acmicpc.net/problem/4386 ✨ 자바로 푸는 별자리 만들기 문제 풀이 📌 문제 개요 백준 4386번 “별자리 만들기”는주어진 N개의 별 좌표를 기반으로 별자리를 만들 때,모든 별을 연결하면서 최소한의 선분 길이 합을 구하는 문제입니다. 즉, 모든 별을 잇되 최소 비용으로 연결하는 구조를 요구하며, 이는 전형적인 최소 신장 트리(MST, Minimum Spanning Tree) 문제입니다. 💡 예제 입력31.0 1.02.0 2.02.0 4.0 예제 출력3.41 🛠 알고리즘 접근 방식 별들 간 거리를 간선으로 보고,이 중에서 가장 적은 거리의 간선들만을 선택해 모든 별을 연결해야 합니다. 이를 위해 프림 알고리즘을 사용합니다.(크루스칼도 가능하지만, 이 코..

🔁 자바로 푸는 사이클 게임 문제 풀이 📌 문제 개요 백준 20040 - 사이클 게임 문제는N개의 정점이 있고, M개의 간선을 순차적으로 연결할 때사이클이 처음 생기는 시점을 출력하는 문제입니다. 간선은 차례로 연결되며,간선을 연결할 때 사이클이 생기면 그 **차례(1-indexed)**를 출력끝까지 사이클이 없으면 0을 출력 💡 예제 입력6 50 11 22 30 34 5 예제 출력4 🧠 알고리즘 접근 방식 이 문제는 전형적인 Union-Find(서로소 집합) 알고리즘을 활용해사이클을 탐지하는 문제입니다. 간선을 하나씩 연결하며, 두 노드가 이미 같은 집합이면 사이클 발생그렇지 않으면 두 집합을 합침 (union)사이클이 생긴 첫 번째 간선의 번호를 출력 🧾 코드 해설// 부모 배열 초기..

https://www.acmicpc.net/problem/9372 🛫 자바로 푸는 상근이의 여행 문제 풀이 📌 문제 개요 백준 9372번 “상근이의 여행” 문제는N개의 국가와 M개의 비행기 노선이 주어졌을 때,모든 국가를 방문할 수 있는 최소한의 비행기 수를 구하는 문제입니다. 비행 노선은 양방향(왕복)입니다.주어진 국가와 노선들은 항상 연결 그래프를 이룹니다.중요한 조건은 “직접 연결된 비행기만 타는 것이 아니라, 경유도 가능“하다는 점입니다. 💡 예제 입력23 31 22 31 35 42 12 34 34 5 예제 출력24 🛠 알고리즘 접근 방식 이 문제는 사실상 그래프 이론 문제이며,그래프가 연결되어 있다는 전제 하에, 모든 노드를 방문하려면 필요한 간선 수는 다음과 같습니다: ✅ 핵..

https://www.acmicpc.net/problem/4195 👥 자바로 푸는 친구 네트워크 문제 풀이 📌 문제 개요 백준 4195번 - 친구 네트워크 문제는여러 명이 친구 관계로 연결될 때,각 관계마다 현재 친구 네트워크의 크기를 출력하는 문제입니다. 친구 관계가 주어짐 (A B → A와 B가 친구)친구 관계가 생길 때마다, A와 B가 속한 전체 네트워크(연결된 집합)의 크기를 출력이름은 문자열로 주어짐 💡 예제 입력23Fred BarneyBarney BettyBetty Wilma3Fred BarneyBetty WilmaBarney Betty 예제 출력2 3 4 2 2 4 🛠 알고리즘 접근 방식 핵심은 Union-Find (Disjoint Set) 알고리즘이름이 문자열이기..

https://www.acmicpc.net/problem/1976 ✈ 자바로 푸는 여행가자 문제 풀이📌 문제 개요 여행 계획에 따라 여러 도시를 순서대로 방문할 수 있는지 판단하는 문제입니다.도시 간의 연결 여부가 주어지며, 여행 경로에 포함된 모든 도시가 **같은 네트워크(연결된 그룹)**에 있어야 합니다. 1은 도시간 연결을 의미하고 0은 연결이 없음을 의미합니다.Union-Find(Disjoint Set)를 활용하여 각 도시가 같은 그룹에 속하는지 판단하면 됩니다. 💡 예제 입력330 1 01 0 10 1 01 2 3출력:YES 🧠 알고리즘 접근 방식 Union-Find 자료구조를 사용해 도시 간 연결 정보를 하나의 집합으로 병합합니다.여행 계획에 포함된 도시들이 **모두 같은 집합..

https://www.acmicpc.net/problem/1717 🧩 자바로 푸는 집합의 표현 문제 풀이 📌 문제 개요 백준 1717번 집합의 표현 문제는 Disjoint Set(서로소 집합) 자료구조의 기본 동작인 Find와 Union을 구현하는 대표적인 문제입니다. 연산 종류0 a b : a와 b가 속한 집합을 합친다.1 a b : a와 b가 같은 집합에 포함되어 있는지 확인한다. 💡 예제 입력7 80 1 31 1 70 7 61 7 10 3 70 4 20 1 11 1 1예제 출력:NONOYES 🧠 알고리즘 접근 방식 핵심은 Union-Find 알고리즘입니다.각 원소는 자신이 속한 집합의 대표(parent)를 가리킵니다.find(x)를 통해 대표를 찾고, union(x, y)를 통해..

https://www.acmicpc.net/problem/2263 📌 자바(Java)로 푸는 트리의 순회 - 백준 2263 🌲 Inorder + Postorder → Preorder 복원하기 🔎 문제 개요 백준 2263 - 트리의 순회 문제는, 이진 트리의 Inorder(중위 순회) 와 Postorder(후위 순회) 결과가 주어질 때,이진 트리의 Preorder(전위 순회) 결과를 출력하는 문제입니다.💡 예제 입력32 1 32 3 1 💡 예제 출력1 2 3 🛠 알고리즘 접근 방식 이 문제는 트리를 직접 복원하지 않고,✔ 순회 결과만을 이용해 바로 Preorder를 만들어내는 것이 핵심입니다. 📌 트리 순회의 특징 이해하기순회 방법순서Preorder(전위 순회)루트 → 왼쪽 → 오른쪽In..