📢 공지합니다
이 게시글은 메인 페이지에 항상 고정되어 표시됩니다.
📌 고정 게시글
최코딩의 개발
[백준 1647번] 도시 분할 계획 || [백준 20040번] 사이클 게임 || [백준 2252번] 줄 세우기 || 음악 프로그램 본문
코딩테스트/백준
[백준 1647번] 도시 분할 계획 || [백준 20040번] 사이클 게임 || [백준 2252번] 줄 세우기 || 음악 프로그램
seung_ho_choi.s 2025. 9. 15. 00:12728x90
https://www.acmicpc.net/problem/1647
package graph;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Graph1674 {
static int N, M;
static boolean[][] visit;
static class Edge implements Comparable<Edge> {
int from;
int to;
int cost;
Edge(int f, int t, int c) {
this.from = f;
this.to = t;
this.cost = c;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
static class UnionFind {
int[] parent;
UnionFind(int n) {
parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]); // 경로 압축
}
boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) return false; // 이미 같은 집합 → 사이클
parent[rootB] = rootA; // 합치기
return true;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
List<Edge> edgeList = new ArrayList<>();
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
visit = new boolean[N + 1][N + 1]; // 사이클 확인용
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
edgeList.add(new Edge(from, to, cost));
}
Collections.sort(edgeList);
int result = simulation(edgeList);
System.out.println(result);
}
private static int simulation(List<Edge> edgeList) {
UnionFind unionFind = new UnionFind(N);
int result = 0;
int maxResult = 0;
for (Edge edge : edgeList) {
if (unionFind.union(edge.from, edge.to)) {
result += edge.cost;
maxResult = edge.cost;
}
}
result -= maxResult;
return result;
}
}
사이클이 핵심이었다. visit로 하려다가 망해버려서 블로그 좀 참고했다.. ㅎㅎㅎ
==========================
https://www.acmicpc.net/problem/20040
package datastructure;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Data20040 {
static int N, M;
static class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) return false;
parent[rootB] = rootA;
return true;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] jum = new int[M][2];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
jum[i][0] = Integer.parseInt(st.nextToken());
jum[i][1] = Integer.parseInt(st.nextToken());
}
int result = simulation(jum);
System.out.println(result);
}
private static int simulation(int[][] jum) {
UnionFind uf = new UnionFind(N);
int result = 0;
for (int cnt = 0; cnt < M; cnt++) {
int startJum = jum[cnt][0];
int endJum = jum[cnt][1];
if (uf.union(startJum, endJum)) {
result++;
} else {
break;
}
}
if (result == M) {
result = 0;
} else {
result += 1;
}
return result;
}
}
도시 분할 계획이랑 비슷한 문제이다. union 함수도 다이스트라나 그래프처럼 외워야겠다. 사이클이 맛도리네~
https://www.acmicpc.net/problem/2252
package graph;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Graph2252 {
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < N + 1; i++) {
graph.add(new ArrayList<>());
}
int[] indegree = new int[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
graph.get(from).add(to);
indegree[to] += 1;
}
simulation(graph, indegree);
}
public static void simulation(List<List<Integer>> graph, int[] indegree) {
Queue<Integer> queue = new LinkedList<>();
StringBuilder result = new StringBuilder();
for (int i = 1; i < N + 1; i++) {
if (indegree[i] == 0) {
queue.add(i);
}
}
while (!queue.isEmpty()) {
Integer poll = queue.poll();
result.append(poll).append(" ");
List<Integer> nodeTo = graph.get(poll);
for (Integer to : nodeTo) {
indegree[to] -= 1;
if (indegree[to] == 0) {
queue.add(to);
}
}
}
System.out.println(result.toString().trim());
}
}
위상정렬 좋다
https://www.acmicpc.net/problem/2623
애는 위에 문제 응용문제!
package graph;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Graph2623 {
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < N + 1; i++) {
graph.add(new ArrayList<>());
}
int[] indegree = new int[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int cnt = Integer.parseInt(st.nextToken());
int from = Integer.parseInt(st.nextToken());
for (int j = 1; j < cnt; j++) {
int to = Integer.parseInt(st.nextToken());
graph.get(from).add(to);
indegree[to] += 1;
from = to;
}
}
simulation(indegree, graph);
}
private static void simulation(int[] indegree, List<List<Integer>> graph) {
StringBuilder result = new StringBuilder();
Queue<Integer> queue = new LinkedList<>();
int count = 0;
for (int i = 1; i < N + 1; i++) {
if (indegree[i] == 0) {
queue.add(i);
}
}
while (!queue.isEmpty()) {
int poll = queue.poll();
result.append(poll).append("\n");
count++;
List<Integer> nodeto = graph.get(poll);
for (Integer to : nodeto) {
indegree[to] -= 1;
if (indegree[to] == 0) {
queue.add(to);
}
}
}
if (count != N) {
System.out.println(0);
} else {
System.out.println(result.toString().trim());
}
}
}
https://www.acmicpc.net/problem/1766
package datastructure;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Data1766 {
static int N, M;
static List<List<Integer>> graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new ArrayList<>();
for (int i = 0; i < N+1; i++) {
graph.add(new ArrayList<>());
}
int[] indegree = new int[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
indegree[b] += 1;
graph.get(a).add(b);
}
simulation(indegree);
}
private static void simulation(int[] indegree) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
pq.add(i);
}
}
while (!pq.isEmpty()) {
Integer pollA = pq.poll();
sb.append(pollA).append(" ");
List<Integer> nodes = graph.get(pollA);
for (Integer node : nodes) {
indegree[node] -= 1;
if (indegree[node] == 0) {
pq.add(node);
}
}
}
System.out.println(sb.toString().trim());
}
}
728x90
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준 17404번] RGB거리 2 (0) | 2025.09.17 |
|---|---|
| [백준 2239번] 스도쿠 (0) | 2025.09.15 |
| [백준 22251번] 빌런 호석 (0) | 2025.09.14 |
| [백준 2668번] 숫자고르기 || [백준 9466번] 텀 프로젝트 (0) | 2025.09.11 |
| [백준 17825번] 주사위 윷놀이 (0) | 2025.09.11 |
'코딩테스트/백준' Related Articles
more
