public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
이 문제에 핵심
1. 준석이는 모든 학생들과 친구가 되고 싶어합니다.
2. 학생과 친구가 되려면 친구비를 지불해야 합니다.
3. 학생의 친구는 친구를 이용해서 모든 친구와 친구가 되는 최소 비용을 결과로 출력합니다.
4. 모든 학생과 친구가 되지 못하면 "Oh no"을 결과로 출력합니다.
5. 친구 관계에서 자기 자신 및 중복된 친구 관계가 입력될 수 있으며, 양방향 관계입니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 비용 낮은 친구들부터 BFS을 통해 최소 비용을 구합니다.
3. 탐색을 통해 얻은 최소 비용을 결과로 출력합니다.
친구 사귀기
모든 학생과 친구가 되어야 하기 때문에 친구비가 작은 친구들부터 사귀기를 진행하여 최대한 친구의 친구를 이용해야 합니다.
학생들의 친구비를 기준으로 오름차순 정렬한 뒤, 해당 친구들부터 친구를 사귀기 진행합니다.
친구의 친구 관계는 BFS을 통해서 탐색을 진행합니다.
BFS을 탐색할 때에는 이미 친구가 된 친구들을 더 이상 친구 맺기를 진행하지 않습니다.
※ 예제입력 과정을 확인하시면 이해하시기 편하실 것입니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
N : 5
M : 3
K : 20
친구비
친구
1
2
3
4
5
비용
10
10
20
20
30
학생과 친구 관계 그래프 형성
2. 비용 낮은 친구들부터 BFS을 통해 최소 비용을 구합니다.
친구비 기준 오름차순 정렬
친구
1
2
3
4
5
비용
10
10
20
20
30
가장 친구비가 낮은 친구1부터 친구 맺기 진행
친구 : { 1, 3}
현재 사용한 비용 : 10
친구
1
2
3
4
5
비용
10
10
20
20
30
가장 친구비가 낮은 친구2부터 친구 맺기 진행
친구 : { 1, 2, 3, 4, 5}
현재 사용한 비용 : 20
친구
1
2
3
4
5
비용
10
10
20
20
30
모두 친구가 되었습니다.
3. 탐색을 통해 얻은 최소 비용을 결과로 출력합니다.
모든 학생과 친구가 되었을 때 최소 비용 : 20
20을 결과로 출력합니다.
BufferedReader를 사용하여 입력되는 정보를 저장합니다.
StringTokenizer를 이용하여 친구 비용 및 친구 관계를 띄어쓰기 기준 저장합니다.
Arrays.sort()을 통해서 친구비 기준 오름차순 정렬하였습니다.
친구비가 낮은 학생부터 search함수를 통해 친구 맺기를 진행합니다.
친구맺기가 끝난 뒤 모두 친구가 되었으면 비용, 아니면 "Oh no"을 결과로BufferedWriter저장합니다.
BufferedWriter에 저장된 결과를 출력합니다.
search함수는 BFS을 통해서 친구의 친구 맺기를 진행합니다.
checkFriends함수는 모든 학생과 친구인지 확인하는 함수입니다.
결과코드
import java.io.*;
import java.util.*;
public class Main {
//친구비 관련 클래스
static class Cost implements Comparable<Cost>{
//idx : 친구 번호, cost : 친구비
int idx, cost;
Cost(int idx, int cost){
this.idx = idx;
this.cost = cost;
}
//친구비 기준 오름차순 정렬
@Override
public int compareTo(Cost o) {
return this.cost - o.cost;
}
}
//친구 관계 관련 그래프
static List<List<Integer>> graph = new ArrayList<>();
//친구 맺기 확인 배열
static boolean[] visited;
static int N;
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
//N, M, K 정보 저장
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
//배열 초기화
Cost[] costs = new Cost[N];
visited = new boolean[N+1];
st = new StringTokenizer(br.readLine()," ");
//그래프 초기화
for(int i=0;i<=N;i++){
graph.add(new ArrayList<>());
}
//친구비 저장
for(int i=0;i<N;i++){
costs[i] = new Cost(i+1, Integer.parseInt(st.nextToken()));
}
//친구 관계 설정
for(int i=0;i<M;i++){
st = new StringTokenizer(br.readLine()," ");
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
//자기 자신일 때 넘기기
if(v == w){
continue;
}
//친구 양방향 설정
graph.get(v).add(w);
graph.get(w).add(v);
}
//친구비 기준 오름차순 정렬
Arrays.sort(costs);
//모든 친구와 친구 맺은지 확인하는 Flag
boolean flag = false;
int result = 0;
//가장 낮은 친구비와 친구 맺기 진행
for(int i=0;i<N;i++){
int idx = costs[i].idx;
int cost = costs[i].cost;
//이미 친구인 학생
if(visited[idx]){
continue;
}
//지금 가진 비용보다 친구비가 비쌀 때, 모든 친구 맺기 실패
if(cost > K){
break;
}
//친구 맺기 진행
result += cost;
K -= cost;
//bfs을 통해 친구의 친구 맺기 진행
bfs(idx);
//모든 학생과 친구를 맺었는지 확인
if(checkingFriends()){
flag = true;
break;
}
}
//모든 학생과 친구일 때
if(flag){
bw.write(String.valueOf(result));
}else{ //모든 학생과 친구가 아닐 때
bw.write("Oh no");
}
bw.flush(); //결과 출력
bw.close();
br.close();
}
//bfs을 통해서 친구의 친구 관계 맺기
static void bfs(int start){
Queue<Integer> q = new ArrayDeque<>();
visited[start] = true;
q.offer(start);
//bfs 진행
while(!q.isEmpty()){
int cur = q.poll();
//친구의 관계들 탐색
for(int nxt : graph.get(cur)){
//현재 친구를 맺지 않은 학생일 때
if(!visited[nxt]){
visited[nxt] = true;
q.offer(nxt);
}
}
}
}
//모든 학생과 친구를 맺었는지 확인하는 함수
static boolean checkingFriends(){
for(int i=1;i<=N;i++){
//친구가 아닌 학생이 있을 때
if(!visited[i]){
return false;
}
}
//모든 학생과 친구일 때
return true;
}
}
댓글