[백준/JAVA] 1414번: 불우이웃돕기
🔺 문제
1414번: 불우이웃돕기
첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
import java.util.*;
import java.io.*;
public class Main {
static int N, sum;
static int[] parent; // 부모 노드
static PriorityQueue<Edge> pq; // 에지 리스트
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
parent = new int[N];
for(int i = 0 ; i < N ; i++) parent[i] = i;
// 에지 리스트에 저장
pq = new PriorityQueue<>();
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine()," ");
char[] chArr = st.nextToken().toCharArray();
for(int j = 0 ; j < N ; j++) {
int tmp = 0;
if('a' <= chArr[j] && chArr[j] <= 'z') tmp = chArr[j] - 'a' + 1;
else if('A' <= chArr[j] && chArr[j] <= 'Z') tmp = chArr[j] - 'A' + 27;
sum += tmp; // 총 랜선 길이 저장
if(i != j && tmp != 0)
pq.add(new Edge(i, j, tmp));
}
}
// MST 수행 (= 최소 필요한 랜선 길이)
int useEdge = 0;
int result = 0;
while(!pq.isEmpty()) {
Edge now = pq.poll();
if(find(now.s) != find(now.e)) {
union(now.s, now.e);
result += now.v;
useEdge++;
}
}
if(useEdge == N - 1) System.out.println(sum - result);
else System.out.println(-1);
}
// 유니온 파인드
public static void union(int a, int b) {
a = find(a);
b = find(b);
if(a != b) parent[b] = a;
}
public static int find(int a) {
if(a == parent[a]) return a;
else return parent[a] = find(parent[a]);
}
}
class Edge implements Comparable<Edge> {
int s, e, v;
Edge(int s, int e, int v) {
this.s = s;
this.e = e;
this.v = v;
}
@Override
public int compareTo(Edge o) {
return this.v - o.v;
}
}
|
cs |
✅ 해결 아이디어
✔ 최소 신장 트리 - 크루스칼
→ 기부할 수 있는 랜선 길이의 최댓값 = 랜선 길이 총합 - 최소한으로 필요한 랜선 길이 (= MST수행 값)
💥 유의사항
• 입력 받은 값을 굳이 2차원 배열에 넣을 필요 없이, 변수를 사용해 바로 에지 리스트에 값 저장 가능 (변수 tmp)
• 소문자 : 현재 - ' a' + 1; / 대문자 : 현재 - 'A' + 27
• 기부할 수 있는 랜선 길이의 최댓값 = 랜선 길이 총합 - 최소한으로 필요한 랜선 길이 (= MST 수행 값)
🔺 다른 풀이들
- 프림, 크루스칼 방법 모두 사용하심. & 결과 설명 굿
[JAVA] BOJ 1414 불우이웃돕기
방향이 있는 그래프에서 최소 스패닝 트리 구하기 (프림, 크루스칼)
velog.io
- 다익스트라 활용하심
[Java] 백준 1414번 : 불우이웃돕기
1. 문제 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를
yerinpy73.tistory.com
- 에지 리스트 안 쓰시고 인접 리스트 쓰셨고 다른 부분도 참고용
: 소문자 대문자 구분도 Character.isLowerCase() 이런 거 사용하심
[백준, Java] 1414번 : 불우이웃돕기
🔗 문제 링크 https://www.acmicpc.net/problem/1414 😮 문제 해결 방법 문제의 입력이 인접행렬 방식으로 들어오고, 알파벳과 0으로 들어온다. 따라서, 입력이 이어진 랜선의 길이이기 때문에 숫자로 변
zayson.tistory.com
💬 느낀 점
아이디어를 생각하지 못 하면 진짜 못 풀 것 같다...
근데 복습하면 괜찮을 것 같다!
이 MST 흐름에 대한 감이 좀 잡혔다.
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 6/27 |
(+ 6/27 2회독)
다 까묵...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
import java.util.*;
import java.io.*;
public class Main {
static int N, sum;
static PriorityQueue<Edge> pq;
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
// 변수들 초기화하기
parent = new int[N];
for(int i = 0 ; i < N ; i++)
parent[i] = i;
pq = new PriorityQueue<>();
// 에지 리스트에 저장
for(int i = 0 ; i < N ; i++) {
char[] chArr = br.readLine().toCharArray();
for(int j = 0 ; j < chArr.length ; j++) {
int tmp = 0;
if('a' <= chArr[j] && chArr[j] <= 'z') {
tmp = chArr[j] - 'a' + 1;
}
else if('A' <= chArr[j] && chArr[j] <= 'Z') {
tmp = chArr[j] - 'A' + 27;
}
sum += tmp; // 총 랜선 길이 저장
if(i != j && tmp != 0) {
pq.add(new Edge(i, j, tmp));
}
}
}
// MST 수행
int useEdge = 0;
int result = 0;
while(!pq.isEmpty()) {
Edge now = pq.poll();
if(find(now.s) != find(now.e)) {
union(now.s, now.e);
result += now.v;
useEdge++;
}
}
System.out.println((useEdge == N - 1) ? (sum - result) : -1);
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
if(a != b) parent[b] = a;
}
private static int find(int a) {
if(a == parent[a]) return a;
return parent[a] = find(parent[a]);
}
}
class Edge implements Comparable<Edge> {
int s, e, v;
public Edge(int s, int e, int v) {
this.s = s;
this.e = e;
this.v = v;
}
@Override
public int compareTo(Edge edge) {
return this.v - edge.v;
}
}
|
cs |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편