그래프 이론에서 공부 할 내용은 서로소 집합(union-find), 서로소 경로압축, 서로소 집합 사이클,
신장 트리, 크루스칼 알고리즘, 위상정렬이다.
목표
왜 서로소 집합, 경로압축, 그 후 사이클을 해야하고, 신장 트리,크루스칼을 알아야 할까요?
-
- 서로소 집합 경로압축 후 사이클을 판단하여 모든노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 신장트리라고 한다.
-
- 신장트리는 하나만 나올 수있는게 아니라 여러개가 나올 수 있다. 이때 가장적은 값으로 신장트리를 만드는 알고리즘을 크루스칼 알고리즘이라고 한다.
-
즉 우리는 가장적은 값으로 신장트리를 만들기 위해서(최소 비용 신장 트리MST - Minimum Cost Spanning Tree) 서로소 집합, 경로압축 ,사이클 ,신장트리 ,크루스칼 알고리즘을 배운다고 볼 수 있다.
-
크루스칼 알고리즘의 대표적은 문제는 전반적으로 서로를 연결하면서 그 길이가 최소가 되도록 하는 문제에 많이 사용 됩니다.
- 도로 건설 (도시를 모두 연결하고, 도로 길이가 최소가 되도록 하는 문제)
- 전기 회로 (단자들을 모두 연결하면서 전선의 길이가 최소가 되도록 하는 문제)
- 통신 (전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제)
- 배관 (파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제)
그럼 위상정렬을 무엇일까요?
- 방향 그래프의 모든 노드를 '방향성을 거스르지 않도록 순서대로 나열하는 것'이다.
다음 그림을 보면 이해하기 쉽습니다.
이처럼 모든 과목을 들으면서 방향성을 거스르지 않도록 하기 위해선 자료구조 ,알고리즘 ,고급 알고리즘 순으로 들어야합니다.
이제 서론은 끝났고 서로소집합부터 시작하겠습니다.
서로소 집합
수학에서 서로소 집합 (Disjoint Sets) 란 공통 원소가 없는 두집합을 의미합니다.
- 서로소 집합의 가장 중요한 기능은 두가지입니다. union(합집합), find(찾기)
알고리즘은 다음과 같습니다.
- union 연산을 통해서 서로 연결된 두 노드 A,B 를 확인한다.
1)A와 B의 루트노드 A',B'를 각각 찾는다.
2) 크기 비교를 통해 A',B' 를 설정한다.
2.모든 union 연산을 처리 할 때까지 1번과정을 반복한다.
구현코드:
import java.util.*;
import java.io.*;
public class Main {
public static int n;
public static int e;
public static int[] parent;
public static int findParent(int a){
if(a == parent[a]) return a;
else return findParent(parent[a]);
}
public static void unionParent(int a, int b){
a = findParent(a);
b = findParent(b);
if(a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
parent = new int[n+1];
for(int i = 1; i <=n ; i++ ){
parent[i] = i;
}
for(int i = 0; i < e ; i++){
st = new StringTokenizer(br.readLine());
unionParent(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
// 각 원소가 속한 집합 출력하기
System.out.print("각 원소가 속한 집합: ");
for (int i = 1; i <= n; i++) {
System.out.print(findParent(i) + " ");
}
System.out.println();
// 부모 테이블 내용 출력하기
System.out.print("부모 테이블: ");
for (int i = 1; i <= n; i++) {
System.out.print(parent[i] + " ");
}
System.out.println();
}
}입력예시:
6 4
1 4
2 3
2 4
5 6
출력예시:
각 원소가 속한 집합: 1 1 1 1 5 5
부모 테이블: 1 1 2 1 5 5
서로소집합 경로 압축기법
- 이 과정엔 비효율적이기 때문에 경로 압축기법을 활용해야 한다.
구현코드:
import java.util.*;
import java.io.*;
public class Main {
public static int n;
public static int e;
public static int[] parent;
public static int findParent(int a){
if(a == parent[a]) return a;
return parent[a] = findParent(parent[a]);
}
public static void unionParent(int a, int b){
a = findParent(a);
b = findParent(b);
if(a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
parent = new int[n+1];
for(int i = 1; i <=n ; i++ ){
parent[i] = i;
}
for(int i = 0; i < e ; i++){
st = new StringTokenizer(br.readLine());
unionParent(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
// 각 원소가 속한 집합 출력하기
System.out.print("각 원소가 속한 집합: ");
for (int i = 1; i <= n; i++) {
System.out.print(findParent(i) + " ");
}
System.out.println();
// 부모 테이블 내용 출력하기
System.out.print("부모 테이블: ");
for (int i = 1; i <= n; i++) {
System.out.print(parent[i] + " ");
}
System.out.println();
}
}입력예시:
6 4
1 4
2 3
2 4
5 6
출력예시:
각 원소가 속한 집합: 1 1 1 1 5 5
부모 테이블: 1 1 1 1 5 5
서로소 집합 사이클판별
서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용 할 수 있다는 특징이 있습니다. 즉 방향그래프일 땐 사용 불가.
-
아래의 4가지 사진을 보자.
-
우리가 사이클을 판별 하는 이유는 무엇이라 했는가?
-
즉 ! 신장트리를 만들기 위해서다. 신장트리란 위에서도 말했던것과 마찬가지로 모든노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
-
사이클을 판별하기 위해선 다음과같다. 먼저 union 연산을 하기전에 두 노드들의 parent[A] == parent[B] 를 비교해서 맞다면 이 것은 사이클이 되고있다는 것이다.
우선 코드를 확인하자.
구현코드:
import java.util.*;
public class Main {
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int v, e;
public static int[] parent = new int[100001]; // 부모 테이블 초기화하기
// 특정 원소가 속한 집합을 찾기
public static int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
boolean cycle = false; // 사이클 발생 여부
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
// 사이클이 발생한 경우 종료
if (findParent(a) == findParent(b)) {
cycle = true;
break;
}
// 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
else {
unionParent(a, b);
}
}
if (cycle) {
System.out.println("사이클이 발생했습니다.");
}
else {
System.out.println("사이클이 발생하지 않았습니다.");
}
}
}입력예시:
3 3
1 2
1 3
2 3
출력예시
사이클이 발생했습니다.
크루스칼 알고리즘
위에서 말했던 것과 같이 초소한의 비용으로 신장 트리를 찾아야할 때 사용한다고 보면된다 . 즉 지금까지 코드들을 종합적으로 합쳐서 만들면 된다.
크루스칼 알고리즘 설명:
- 대표적인 최소 신장 트리 알고리즘입니다.
- 그리디 알고리즘으로 분류됩니다.
- 구체적인 동작과정은 다음과 같습니다.
1. 간선의 데이터를 비용에 따라 오름차순 으로 정렬합니다.
2.간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인합니다.
1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킵니다.
2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않습니다.
- 모든 간선에 대하여 2번과정을 반복합니다.
- 크루스칼 알고리즘의 성능분석은 간선의 개수가 E 일 때 O(ElogE) 의 시간복잡도를 가집니다.
구현코드:
import java.util.*;
import java.io.*;
class Edge implements Comparable<Edge>{
private int distance;
private int node1;
private int node2;
public Edge(int node1, int node2, int distance){
this.distance = distance;
this.node1 = node1;
this.node2 = node2;
}
public int getDistance(){
return this.distance;
}
public int getNode1(){
return this.node1;
}
public int getNode2(){
return this.node2;
}
@Override
public int compareTo(Edge other){
return this.distance < other.distance ? -1 : 1;
}
}
public class Main{
public static int v;
public static int e;
public static int[] parent;
public static ArrayList<Edge>edge = new ArrayList<>();
public static int findParent(int x){
if(x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
public static void unionParent(int a, int b){
a = findParent(a);
b = findParent(b);
if(a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
parent = new int[v+1];
for(int i = 1 ;i <=v; i++){
parent[i] = i;
}
for(int i = 0 ;i < e; i++){
st = new StringTokenizer(br.readLine());
edge.add(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
Collections.sort(edge);
int sum = 0;
for(int i = 0 ;i < e; i++){
int node1 = edge.get(i).getNode1();
int node2 = edge.get(i).getNode2();
int distance = edge.get(i).getDistance();
if(findParent(node1) == findParent(node2)) continue;
unionParent(node1, node2);
sum += distance;
}
System.out.println(sum);
}
}입력예제:
7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25
출력예제
159
코드설명을 한다면 다음과 같다.
가장적은 간선부터 판단한다. 그렇기 위햐서 정렬을 사용했다. 또한 사이클이 아닐때union을 해주면 된다. 그리고 거리를 합해주면 된다. 이 과정까지가 힘든 것이지 알고나면 쉬운 알고리즘이다.
위상정렬
그럼 위상정렬을 무엇일까요?
방향 그래프의 모든 노드를 '방향성을 거스르지 않도록 순서대로 나열하는 것'이다.
- 다음 그림을 보면 이해하기 쉽습니다.
이처럼 모든 과목을 들으면서 방향성을 거스르지 않도록 하기 위해선 자료구조 ,알고리즘 ,고급 알고리즘 순으로 들어야합니다.
이처럼 구현하기 위해선 우리는 '집입차수' 만 생각해서 코드를 구현하면 됩니다.
-
맨처음 시작점은 진입차수가 0입니다.
-
진입차수가 0인 것을 queue에 넣습니다. 그 후 queue 에들어있는 1을 빼고 1과 연결된 간선을 제거합니다.
-
이과정을 만복하면
-
모든 노드가 queue 에서 빠져나오게 되고
-
1 → 2 → 5 → 3 → 6 → 4 → 7가 됩니다.
구현코드:
import java.util.*;
public class Main {
// 노드의 개수(V)와 간선의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int v, e;
// 모든 노드에 대한 진입차수는 0으로 초기화
public static int[] indegree = new int[100001];
// 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// 위상 정렬 함수
public static void topologySort() {
ArrayList<Integer> result = new ArrayList<>(); // 알고리즘 수행 결과를 담을 리스트
Queue<Integer> q = new LinkedList<>(); // 큐 라이브러리 사용
// 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for (int i = 1; i <= v; i++) {
if (indegree[i] == 0) {
q.offer(i);
}
}
// 큐가 빌 때까지 반복
while (!q.isEmpty()) {
// 큐에서 원소 꺼내기
int now = q.poll();
result.add(now);
// 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for (int i = 0; i < graph.get(now).size(); i++) {
indegree[graph.get(now).get(i)] -= 1;
// 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if (indegree[graph.get(now).get(i)] == 0) {
q.offer(graph.get(now).get(i));
}
}
}
// 위상 정렬을 수행한 결과 출력
for (int i = 0; i < result.size(); i++) {
System.out.print(result.get(i) + " ");
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 그래프 초기화
for (int i = 0; i <= v; i++) {
graph.add(new ArrayList<Integer>());
}
// 방향 그래프의 모든 간선 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph.get(a).add(b); // 정점 A에서 B로 이동 가능
// 진입 차수를 1 증가
indegree[b] += 1;
}
topologySort();
}
}입력예제
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
출력예제
1 2 5 3 6 4 7
실전문제 1. 팀 결성
문제요약:
학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다.
'팀 합치기' 연산은 두 팀을 합치는 연산이다.
'같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.
선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.
입력 조건
첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 ≤ N, M ≤ 100,000)
다음 M개의 줄에는 각각의 연산이 주어진다.
'팀 합치기' 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미이다.
'같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다. 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는지를 확인하는 연산이다.
a와 b는 N 이하의 양의 정수이다.
출력 조건
'같은 팀 여부 확인' 연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.
입력 예시 :
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
출력 예시 :
NO
NO
YES
구현코듸
import java.util.*;
import java.io.*;
public class Main{
public static int n, m;
public static int[] parent;
public static int findParent(int x) {
if(x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a < b ) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
parent = new int[n+1];
for(int i = 1; i<=n;i++) {
parent[i] = i;
}
for(int i = 0;i < m ; i++) {
st = new StringTokenizer(br.readLine());
int category = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(category == 0) {
unionParent(a,b);
}else {
if(findParent(a) == findParent(b)) System.out.println("YES");
else System.out.println("NO");
}
}
}
}
코드해석:
구현 코드는 다음과 같다. 서로소 집합을 구현 할 수있다면 풀수있는문제이다. 원래는 모두 서로 다른 팀이라고 하는 것은 초기화 상태를 의미하고 서로소 집합에 합치기 가 원래 구현되어 있기 때문에 0일 땐 합치기 1일때는 parent 가 같은지 확인하면 된다.
실전문제 2.도시 분할 계획
문제요약:
동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다.
마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.입력 조건
첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2 이상 100,000 이하인 정수이고, M 은 1이상 1,000,000 이하인 정수이다.
그다음 줄부터 M줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C(1≤ C ≤ 1,000)라는 뜻이다.
출력 조건
첫째 줄에 길을 없애고 남은 유지비 합의 최솟값을 출력한다.
입력 예시
7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4
출력 예시
8
구현코드:
import java.util.*;
import java.io.*;
class Edge implements Comparable<Edge>{
private int cost;
private int nodeA;
private int nodeB;
public int getCost() {
return this.cost;
}
public int getNodeA() {
return this.nodeA;
}
public int getNodeB() {
return this.nodeB;
}
Edge(int nodeA, int nodeB, int cost){
this.nodeA = nodeA;
this.nodeB = nodeB;
this.cost = cost;
}
@Override
public int compareTo(Edge other) {
return this.cost < other.cost ? -1 : 1;
}
}
public class Main {
public static int n, m;
public static int parent[];
public static ArrayList<Edge>edges = new ArrayList<>();
public static int findParent(int x) {
if(x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
public static void unionParent(int a,int b) {
a = findParent(a);
b = findParent(b);
if(a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
parent = new int[n+1];
for(int i = 1 ; i <=n ; i++) {
parent[i] = i;
}
for(int i = 0 ; i <m ; i++) {
st = new StringTokenizer(br.readLine());
edges.add(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
Collections.sort(edges);
int max = 0;
int sum = 0;
for(int i = 0 ; i < edges.size(); i ++) {
int nodeA = edges.get(i).getNodeA();
int nodeB = edges.get(i).getNodeB();
int cost = edges.get(i).getCost();
if(findParent(nodeA) != findParent(nodeB)) {
unionParent(nodeA,nodeB);
max = Math.max(max,cost);
sum +=cost;
}
}
System.out.println(sum-max);
}
}
코드해석: 나는 이문제를 보고 바로 크루스칼 알고리즘(mst) 를 구하는 문제이구나 파악을 했다.
여기서 중요한 것은 문제의 또다른의도 즉 2개로 나눈다의 의미를 깨달아야한다. 그때 중요한 것은 우리는 최단 신장트리를 찾고 거기서 가장 큰값을 빼면 된다는 것이다.
실전 문제 3. 커리큘럼
문제요약:
철수는 온라인으로 컴퓨터공학강의를 듣고 있다.
이때 각 온라인강의는 선수강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저. 들어야만 해당강의를 들을 수 있다.
예를들어 '알고리즘’ 강의의 선수 강의로 '자료구조'가 존재한다면, ‘자료구조를 들은 이후에 ‘알고리즘' 강의를 들을 수 있다.
철수는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다.
또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다.
예를 들어 N=3일 때, 3번강의의 선수 강의로 1번과 2번강의가 있고, 1번과 2번강의는 선수강의가 없다고 가정하자.
그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정하자.
1번 강의: 30시간
2번 강의: 20시간
3번 강의: 40시간
이 경우 1번 강의를 수강하기까지의 최소 시간은 30시간, 2번 강의를 수강하기까지의 최소 시간은 20시간, 3번 강의를 수강하기까지의 최소 시간은 70시간이다.
철수가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.
- 입력 조건
첫째줄에 철수가 듣고자 하는 강의의 수 N(1≤N≤500)이 주어진다.
다음 N개의 줄에는 각 강의의 강의 시간과 그. 강의를 듣기 위해 먼저 들어야하는 강의들의 번호가 자연수로 주어지며, 각. 자연수는 공백으로 구분한다. 이때 강의시간은 100,000이하의 자연수이다 .각 강의번호는 1부터 N까지로 구성되며. 각줄은 -1로 끝난다.
- 출력 조건
N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력한다
입력 예시
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1
출력 예시
10
20
14
18
17
구현코드:
import java.util.*;
import java.io.*;
public class Main {
public static ArrayList<ArrayList<Integer>>graph = new ArrayList<ArrayList<Integer>>();
public static int[] time;
public static int[] count;
public static int n;
public static void topologySort() {
//ArrayList<Integer>list = new ArrayList<>();
Queue<Integer>queue = new LinkedList<>();
int[] result = new int[n+1];
for(int i = 0 ; i <= n ; i ++) {
result[i] = time[i];
}
for(int i = 1 ; i <= n ; i++) {
if(count[i] == 0) {
queue.offer(i);
}
}
while(!queue.isEmpty()) {
int k = queue.poll();
//list = graph.get(k);
for(int i = 0 ; i <graph.get(k).size();i++) {
count[graph.get(k).get(i)]--;
result[graph.get(k).get(i)]= Math.max(result[graph.get(k).get(i)], result[k]+ time[graph.get(k).get(i)]);
if(count[graph.get(k).get(i)] == 0) {
queue.offer(graph.get(k).get(i));
}
}
}
for(int i =1; i <=n ; i++) {
System.out.println(result[i]);
}
}
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
time = new int[n+1];
count = new int[n+1];
for(int i = 0 ; i <=n ; i++) {
graph.add(new ArrayList<Integer>());
}
for(int i = 1 ; i <= n; i ++) {
StringTokenizer st = new StringTokenizer(br.readLine());
time[i] = Integer.parseInt(st.nextToken());
while(st.hasMoreTokens()) {
int k = Integer.parseInt(st.nextToken());
if(k == -1) break;
graph.get(k).add(i);
count[i]++;
}
}
topologySort();
}
}
코드해석:
문제를 풀면서 가장 어려웠던점은 값의 중첩이였다. 나는 배열 하나로 해결하려고 했던거 같다. 두개를 이용하여 사용하는 것이 best 그 이외엔 대표유형이기 때문에 힘든건 없었다.
이제 이론과 실전문제에 대해서 끝이났다. 주말을 활용해서 이론,실전문제 빠르게 훑어보고 알고리즘 유형별 기출문제 풀어보자!! 하나 끝냈다는 생각에 기분 좋지만 더 힘내서 해보자. ㅎㅇㅌ
