알고리즘 및 코테 복습 - 그래프(Graph)

⬛ 08. 그래프

⬛ 08-1. 그래프의 표현

1. 에지 리스트 : 엣지 중심으로 그래프를 표현
2. 인접 행렬 : 노드 중심으로 그래프를 표현
3. 인접 리스트 : 노드 중심으로 그래프를 표현 ****

⬛ 08-2. 유니온 파인드

• 특정 2개의 노드 연결 union 하고, 집합 여부 판별 find 하기
• 특정 2개의 노드를 연결하여 1개의 집합으로 묶은 Unioin연산, 두 노드가 같은 집합 소속인지 확인하는 Find 연산

⚫ 백준 1717번. 집합의 표현

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

package to_0803_1;

import java.util.ArrayList;
import java.util.Scanner;

//유니온파인드 섹션 - 백준 1717번. 집합의 표현 
public class Main {
	static int[] parent;// 부모 집합 
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else {
			return parent[a] = find(parent[a]);
		}
	}
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;//합치기 
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int n = kb.nextInt(); //원소 개수 
		int m = kb.nextInt();//질의 개수 
		
		parent = new int[n+1];
		for(int i=1; i<=n; i++) parent[i]=  i;//자기 자신으로 초기화 
		
		ArrayList<String> answer = new ArrayList<>();
		
		//데이터 입력받기 
		for(int i=0; i<m; i++) {
			int q = kb.nextInt();
			int a = kb.nextInt();
			int b = kb.nextInt();
			
			if(q == 0) { //0이면 합치기 
				union(a, b);
			}else { //1이면 find로 두 원소 부모 같은지 여부 따지기 
				int x= find(a);
				int y = find(b);
				
				if(x == y) { //둘이 부모가 같다. 
					answer.add("YES");
				}else if(x != y) {
					answer.add("NO");
				}
			}
		}
		//답출력 
		for(String x : answer) {
			System.out.println(x);
		}
	}
}

 

⚫ 백준 1976번. 여행 가자

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

package to_0906_2;

import java.util.Scanner;

/*1976번. 여행 가자 - 유니온 파인드 */
public class Main {
	static int n, m; //m은 여행계획속도시수 
	static int[] parent;
	static int[][] map;
	static int[] route;//계획한 여행 도시 담기 - m개
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		map = new int[n+1][n+1];
		parent = new int[n+1];
		//parent 초기ㅗ하
		for(int i=1; i<=n; i++) parent[i]= i;
	
	
		//입력받기 
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				map[i][j] = kb.nextInt();
			}
		}
		route = new int[m+1];//얘 도시 계획 담긴 배열 
		//동혁이의 여행 계획 담기 
		for(int i=1; i<=m; i++) route[i]= kb.nextInt();
		
		//이제 각 map 돌면서 1인 값에 대해서는 union 처리 
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(map[i][j] == 1) {
					union(i, j);//경로 합치기 
				}
			}
		}
		
		//이제 각 도시별 부모 도시 찾아서 하나라도 다른 도시 나오면 X 모두 같으면 O
		
		//첫번째 도시의 부모는 미리 찾아둠 
		int tmp = find(route[1]);
		
		for(int i=2; i<route.length; i++) { //그 뒷쪽 루트도시의 부모도시가 하나라도 1번이랑 다르다면 
			if(tmp != find(route[i])) { //뒷 부분 루트 순회하면서 
				//하나라도 1번의 부모와 다른 부모 나타나면 
				System.out.println("NO"); //안속해 있음
				return;//걍 여기서 끝 
			}
		}
		//아니라면 탈출해서 YES
		System.out.println("YES");
	}
}

 

 

---

⬛ 08-3. 위상정렬

• 사이클 없는 방향 그래프에서 ‘노드 간 순서 결정’ 알고리즘
• 사이클이 없어야 하고, 사이클 존재하면 명확히 순서 결정이 불가능하다.
• 인접 리스트로 표현
• 사이클 없는 방향 그래프에서 노드 간 순서 결정하는 알고리즘
• 반드시 사이클이 없어야 명확하게 순서 결정 가능

1) 진입차수 0인 노드 큐에 저장 (출발점이니까)

2) 큐에서 데이터 poll() 후 경로에 추가, 해당 노드가 가리키는 인접정점들의 진입차수 D[] 의 값 1씩 뺌

3) 감소한 상태의 진입차수 0인 애들은 다시 큐에 add

4) 큐가 빌 때까지 1~3 반복

 

⚫ 백준 2252번. 줄 세우기

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

• 진입차수 배열 [] 생성해서, 해당 진입차수 0 인 애들이 매번 큐에 담겨져서 출발점 갱신하는 게 핵심
• 큐에서 poll() 한 애는 현재 경로로 찍고, 해당 정점의 인접정점들 순회하면서 진입차수 -1 처리 한다. 뺀 뒤에 다시 진입차수 0인에는 Q에 담고, Q가 빈 상태가 될 때까지 반복하다보면, 위상정렬 노드의 방문 순서가 결정된다.

package to_0803_2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//위상 정렬 섹션 - 백준 2252번. 줄 세우기 
public class Main {
	
	//실행메인
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		
		
		int n = kb.nextInt();//노드 개수
		int m = kb.nextInt();//간선 개수 
		
		int[] indegree = new int[n+1];//진입차수 저장용 
		
		for(int i=0; i<=n; i++) {
			graph.add(new ArrayList<Integer>());//공간 생성 
		}
		
		//데이터 입력 받기 
		for(int i=0; i<m; i++) {
			int a = kb.nextInt();//a 가 
			int b = kb.nextInt();//b에 진입함
			
			graph.get(a).add(b);//방향 a->b를 향함 
			indegree[b]++;//진입당하는 애는 ++ 처리 
		}
		
		//이제 위상정렬 알고리즘 
		Queue<Integer> Q = new LinkedList<>();//큐 생성 
		
		for(int i=1; i<=n; i++) { //정점 차례로 순회하면서 일단 진입차수 0인 애들 다 담음
			if(indegree[i] == 0) {
				Q.add(i);
			}
		}
		
		ArrayList<Integer> answer = new ArrayList<>();
		
		while(!Q.isEmpty()) {
			int cur = Q.poll();
			//여기서 경로 뽑기 
			answer.add(cur);
			for(int nx : graph.get(cur)) { //뽑은 정점의 인접 정점들의 진입차수 --
				indegree[nx]--;
				if(indegree[nx]==0) Q.add(nx);//0인 애는 또 담기 
			}
		}
		
		//정답 출력 
		for(int x : answer)System.out.print(x+ " ");
	}
}

 

⚫ 백준 1516번. 게임 개발 - 위상정렬 문풀

https://www.acmicpc.net/problem/1516

1516번: 게임 개발

import java.util.*;

/*1516번. 게임 개발 -위상정렬 문풀 */
public class Main {
	static int N;
	static int[] cost;//각자 건물 짓는 기본 시간 
	static int[] indegree;//진입차수 
	static int[] dy; //시간 누적용 DP
	static ArrayList<ArrayList<Integer>> graph;
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		N = kb.nextInt();
		cost = new int[N+1];
		indegree = new int[N+1];
		dy = new int[N+1];
		
		graph = new ArrayList<>();
		
		for(int i=0; i<=N; i++ ) graph.add(new ArrayList<>());
		
		//데이터 입력받기 
		for(int i=1; i<=N; i++) {
			int a=  kb.nextInt();
			cost[i] = a;//각 건물 짓는 비용 담기 
			
			while(true) {
				int b = kb.nextInt();//직전에 짓는 건물 번호 담기 i
				
				if(b == -1) break;
				
				//아니면 
				graph.get(b).add(i);//b먼저 짓고 i를 지어야 한다.
				//진입차수는
				indegree[i]++;//현재 i를 기준으로 ++처리 
			}
		}
		
		//위상정렬 처리 
		Queue<Integer> Q = new LinkedList<>();
		
		for(int i=1; i<=N; i++) {
			dy[i] = cost[i];//여기서 미리 담아두기 자기 건물 짓는 시간 
			if(indegree[i] == 0) Q.offer(i);//담기 
		}
		
		while(!Q.isEmpty()) {
			int cur = Q.poll();
			
			for(int nx : graph.get(cur)) {
				indegree[nx]--;
				//여기서 시간 : 직전 건물 시간 + 현재 건물 짓는 시간으로  갱신 
				dy[nx] = Math.max(dy[nx], dy[cur] + cost[nx]);
				
				if(indegree[nx]==0) Q.offer(nx);
			}
		}
		
		for(int i=1; i<=N; i++) {
			System.out.println(dy[i]);
		}
		
	}
}

 

---

 

🏓그래프의 최단 거리 구하는 알고리즘

1. 다익스트라 : one to one : (엣지 모두 양수)
2. 벨만-포드 : one to one : (엣지 양수 + 음수 가능 )
3. 플로이드-와샬 : all to all

⬛ 08-4. 다익스트라

• 인접 리스트로 표현
• 엣지가 모두 양수이다.

1. 인접리스트로 그래프 표현 : ArrayList<ArrayList<Node>> graph
2. 최단거리 distance[] 배열 초기화 Integer.MAX_VALUE
3. 시작점 초기화

distnace[S] = 0;//자기자신은 거리 0

pQ.add(new Node(S, 0) );// 자기 자신, 거리 0 담기

1. while(!pQ.isEmpty() 인 동안

현재 정점 cur 뽑아서. 해당 정점 방문 전인 경우, 방문처리 .

방문처리 후 cur의 인접정점들 순회하면서 nx 정점이 방문 전이면서, 기존 nx 거리 vs 현재 cv 거쳐서 nx 도착 거리가 더 작은 경우 갱신 처리 후 pQ에 삽입

⚫ 백준 1753번. 최단 경로 | 다익스트라

package to_0803_4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

//다익스트라 - 최단경로 1753번. 
class Node implements Comparable<Node>{
	int v;//정점
	int val; //가중치 
	
	Node(int v, int val){
		this.v = v;
		this.val = val;
	}
	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return this.val - o.val;//가중치 적은 애 우선 
	}
}

public class Main {
	static int[] distance;//거리 배열 
	static boolean[] visited;//방문체크용 
	static ArrayList<ArrayList<Node>> graph; 
	
	//실행메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int V= kb.nextInt();
		int E = kb.nextInt();
		int K = kb.nextInt();
		
		//초기화
		distance = new int[V+1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		visited = new boolean[V+1];
		graph = new ArrayList<>();
		
		for(int i=0; i<=V; i++) {
			graph.add(new ArrayList<Node>());
		}
		
		//데이터 입력받기
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b= kb.nextInt();
			int w = kb.nextInt();
			graph.get(a).add(new Node(b, w));//방향 그래프
		}
		
		
		//다익스트라 시작 
		PriorityQueue<Node> pQ = new PriorityQueue<>();
		
		//1) 시작점 처리
		distance[K] = 0;
		pQ.add(new Node(K, 0));//자기 자신까지의 거리는 0으로 세팅
		
		//2) 현재 정점 poll시켜서 방문터리하고 nx 정점 찾아서 최단 경로 갱신 
		while(!pQ.isEmpty()) {
			Node cur = pQ.poll();
			int c_v = cur.v;
			int c_val = cur.val;
			if(!visited[c_v]) { //꺼낸 애가 아직 방문 전인 애면 
				visited[c_v] = true;//방문처리하고 
				
				for(Node nx : graph.get(c_v)) {//그 인접정점에 대하여 
					int nx_v = nx.v;
					int nx_val = nx.val;
					if(!visited[nx_v] && distance[nx_v] > distance[c_v] + nx_val) {
						distance[nx_v] = distance[c_v] + nx_val;
						pQ.add(new Node(nx_v, distance[nx_v]));
					}
				}
			}
		}
		//3) 출력할 정답 처리 
		for(int i=1; i<=V; i++) {
			if(distance[i] == Integer.MAX_VALUE || !visited[i]) {
				System.out.println("INF");
			}else {
				System.out.println(distance[i]);
			}
		}
	}
}

 

⬛ 08-5. 벨만- 포드

• 엣지 리스트로 그래프 표현

1) 에지리스트 그래프 구현 후, 최단경로 배열 초기화

2) 모든 엣지 순회하며 정답 배열을 업데이트

단, 음수 사이클이 없을 때, 최단 거리 구성 가능한 엣지 최대 개수는 N-1이다. (N=노드개수)

3) if(D[s]가 INF이면 방문 전 노드이므로 업데이트X)

&& D[e] > D[s] + w 일때 값 어데이트

4) 다시 한 번 더 모든 엣지 순회하는데 값이 업데이트 된다면 음수 사이클이 존재하는 것임

⚫ 백준 11657번. 타임머신

-for(int i=n-1) 반복하되,

for(int i=0~M) //한번 반복할 때 모든 간선 순회하면서 정답 배열 갱신해주어야 함

그러고 나서 한 번 더 for(int i=0~M) 해주었을 때도 값 갱신 발견되면, 음수 사이클 존재하는 것이므로 관련 처리해줄 것

import java.util.Arrays;
import java.util.Scanner;

//벨만-포드 문제풀이
class Edge {
	int s, e, val;
	Edge(int s, int e, int val){
		this.s=s;
		this.e= e;
		this.val =val;
	}
}
public class Main {
	static final int INF = Integer.MAX_VALUE;
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		int N = kb.nextInt();
		int M = kb.nextInt();
		
		long[] distance = new long[N+1]; 
		Edge[] edges = new Edge[M]; //간선 정보 담기 
		
		Arrays.fill(distance, INF);//초기화 
		
		//데이터 입력받기 
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int v = kb.nextInt();
			edges[i]= new Edge(a, b, v);
		}
		
		//벨만포드 
		//1) 시작정점 처리 
		distance[1]= 0;
		
		//2) N-1번 반복하며 정답배열 세팅 
		for(int i=1; i<N; i++) { //N-1번 반복 
			for(int j=0; j<M; j++) {//1번 반복할 때, 모든 간선 순회하면서 
				Edge cur = edges[j];//현재 엣지에 대하여
				if(distance[cur.s] != INF && distance[cur.e] > distance[cur.s]+cur.val) {
					distance[cur.e] = distance[cur.s] + cur.val;
				}
			}
		}
		
		//3) 음수 사이클 존재 확인 
		boolean cycle = false;
		
		for(int i=0; i<M; i++) {
			Edge cur = edges[i];
			if(distance[cur.s] != INF && distance[cur.e] > distance[cur.s] + cur.val) {
				cycle = true;
			}
		}
		
		if(!cycle) {
			for(int i=2; i<=N; i++) {
				if(distance[i] == INF) {
					System.out.println("-1");
				}else {
					System.out.println(distance[i]);
				}
			}
		}else { //사이클 존재할 경우 
			//즉, 만약 무한히 시간을 오려잰으로 돌릴 수 있다면에 해당 
			System.out.println("-1");
		}	
	}
}

⬛ 08-6. 플로이드-워셜

• 인접 행렬, 인접 리스트로 표현

⚫ 백준 11404번. 플로이드

import java.util.Scanner;

//플로이드 - 문제풀이 
public class Main {
	static int[][] distance;//s->e로 가는 최단경로 저장용
	static final int INF = 10000001;//최대 100 X100000 
	//실행메인	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int n = kb.nextInt();//노드 개수 = 도시
		int m = kb.nextInt();//간선 개수 = 노선
		
		//distance 초기화
		distance = new int[n+1][n+1];//도시가 1번~n번까지 존재하므로
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(i==j) distance[i][j] = 0;//자기자신 0 세팅 
				else {
					distance[i][j] = INF;//제일 큰 값으로 초기확 
				}
			}
		}
		
		//입력 데이터 얻기
		for(int i=0; i<m; i++) {
			int a = kb.nextInt();
			int b= kb.nextInt();
			int val = kb.nextInt();
			if(distance[a][b] > val) {
				distance[a][b]= val;
			}
		}
		
		//플로이드 알고리즘 시작 
		for(int k=1; k<=n; k++) { //경유지 하나씩 설정해보는 거임 
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=n; j++) {
					if(distance[i][j]> distance[i][k] + distance[k][j]) {
						distance[i][j] = distance[i][k] + distance[k][j];//경로 갱신 최단 거리로
					}
				}
			}
		}
		
		//출력
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(distance[i][j] == INF) {
					System.out.print("0 ");
				}else {
					System.out.print(distance[i][j]+" ");
				}
			}
			System.out.println();//출력
		}
	}

}

⚫ 백준 1389번. 케빈 베이컨의 6단계 법칙

package to_0803_7;

import java.util.Scanner;

//1389번. 케빈 베이컨의 6단계 법칙 
public class Main {
	static int[][] distance;//관계 거리 
	static final int INF = 1000001;
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		int n = kb.nextInt();
		int m = kb.nextInt();
		
		distance = new int[n+1][n+1];//1번부터라서 
		
		//distance 초기화
		for(int i=1; i<=n; i++) {
			for(int j =1; j<=n; j++) {
				if(i==j) distance[i][j] = 0;
				else {
					distance[i][j] = INF;
				}
			}
		}
		
		//입력받기 
		for(int i=0; i<m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			distance[a][b] = 1;//양방향 서로 친구이니까 
			distance[b][a] = 1;
		}
		
		//다익스트라 시작 
		for(int k=1; k<=n; k++) {
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=n; j++) {
					if(distance[i][j] > distance[i][k] + distance[k][j]) {
						distance[i][j] = distance[i][k] + distance[k][j];
					}
				}
			}
		}
		
		//각 학생의 베이컨 수 중 가장 작은 값을 갖는 애의 번호 출력 
		int min = Integer.MAX_VALUE;
		int ans_idx = 0;
		
		for(int i=1; i<=n; i++) {
			int tmp = 0;
			for(int j=1; j<=n; j++) {
				tmp += distance[i][j];//각 i행 합 구하고 
			}
			if(tmp < min) {
				min = tmp;
				ans_idx = i;
			}
		}		
		System.out.println(ans_idx);
	}
}

⬛ 08-7. 최소비용 신장트리

• 엣지 리스트로 표현
• 최소비용 신장트리 : 정점 n개, 간선 n-1개, 사이클X 연결그래프인 신장트리이면서 총 간선의 가중치 합 최소인 것
• 그래프의 모든 노드 연결하는 부분 그래프 중 가중치 합이 최소인 것

 

⚫ 백준 1197번. 최소 스패닝 트리

package to_0803_8;

import java.util.PriorityQueue;
import java.util.Scanner;

//최소비용 신장트리 - 백준 1197번. 최소 스패닝 트리 
class Edge implements Comparable<Edge>{
	int s, e, val;
	Edge(int s, int e, int val){
		this.s =s;
		this.e =e;
		this.val =val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val; //가중치 오름차순 정렬 
	}
}
public class Main {
	static int[] parent;//부모 확인 
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else {
			return parent[a] = find(parent[a]);
		}
	}
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a!=b) {
			parent[b] = a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int V = kb.nextInt();//정점 개수 
		int E = kb.nextInt();//간선 개수 
		
		parent = new int[V+1];
		for(int i=1; i<=V; i++) {
			parent[i] = i;//초기화
		}

		PriorityQueue<Edge> pQ= new PriorityQueue<>();
				
		//데이터 입력받기 
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			pQ.add(new Edge(a, b, c));
		}
		
		//최소비용 신장트리 알고리즘 
		int useEdge = 0;
		int answer = 0;
		
		while(useEdge < V-1) {
			Edge cur = pQ.poll();//현재 엣지 뽑고 
			if(find(cur.s) != find(cur.e)) {//사이클 일어나지 않을 경우 
				union(cur.s, cur.e);//둘이 합침
				answer += cur.val;//최소 비용 가중치 합 ++처리 
				useEdge++;
			}
		}		
		System.out.println(answer);	
	}
}