[이것이 코딩테스트다] 9. 그래프 - 실전 문제 풀이

이것이 취업을 위한 코딩테스트다.

 

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

 

 

1. 팀 결성

- 서로소 집합 자료구조를 이용해서 풀이 가능

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	// N : 학생 수
	// M : 연산의 수
	public static int N, M;
	
	// 부모 변수
	public static int[] parent;
	
	// 결과 변수
	public static ArrayList<String> result = new ArrayList<>();
	
	// 특정 원소의 부모 찾기
	public static int findParent(int x) {
		
		// 현재 원소가 부모 그 자체일 경우 x 반환
		if(x == parent[x]) {
			return x;
		}
		
		// 아닐 경우, 그 부모의 부모를 찾고 parent[x]에 대입 및 반환
		return parent[x] = findParent(parent[x]);
	}
	// 팀 합치기 (부모 합치기)
	public static void unionParent(int a, int b) {
		// a의 루트 노드
		int pa = findParent(a);
		
		// b의 루트 노드
		int pb = findParent(b);
		
		// 일반적으로 큰 수가 작은 수를 바라봄
		if(pa<pb) {
			parent[pb] = pa;
		}
		else {
			parent[pa] = pb;
		}
	}
	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=0; i<=N; i++) {
			parent[i] = i;
		}
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int type = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			// 팀 합치기 (부모 합치기)
			if(type==0) {
				unionParent(a,b);
			}
			
			// 같은 팀 여부 확인 (부모 확인)
			else {
				// 부모가 같으면 같은 팀.
				if(parent[a] == parent[b]) {
					result.add("YES");
					
				// 부모가 다르면 다른 팀
				}else {
					result.add("NO");
				}
			}
		}
		
		// 결과 출력
		for(int i=0; i<result.size(); i++) {
			System.out.println(result.get(i));
		}
	}
	

}

 

 

2. 도시 분할 계획

- 크루스칼 알고리즘과 우선순위 큐를 이용하여 해결.

- 최소신장 트리를 2개로 분리한다는 의미 : 간선을 하나만 제거하면 됨.(최소 신장 트리 중 가장 큰 간선을 제거하면 최소 비용이 나옴)

- 백준 문제(https://www.acmicpc.net/problem/1647)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	// N : 집의 수
	// M : 길의 수
	public static int N, M;
	
	// 우선순위 큐
	public static PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
	
	// 부모 배열
	public static int[] parent;
	
	// 간선을 구현하기 위한 class 선언
	public static class Edge implements Comparable<Edge>{
		private int from;
		private int to;
		private int cost;
		
		public Edge(int a, int b, int c) {
			from = a;
			to = b;
			cost = c;
		}

		public int getFrom() {
			return from;
		}

		public void setFrom(int from) {
			this.from = from;
		}

		public int getTo() {
			return to;
		}

		public void setTo(int to) {
			this.to = to;
		}

		public int getCost() {
			return cost;
		}

		public void setCost(int cost) {
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Edge other) {
			if(this.cost < other.cost)
				return -1;
			else
				return 1;
		}
	}
	
	// 부모 찾기 (집합 찾기)
	public static int findParent(int x) {
		// 루트노드가 자신일 경우 반환
		if(x == parent[x]) {
			return x;
		}
		
		// 루트노드를 끝까지 찾아서 parent에 넣고 반환
		return parent[x] = findParent(parent[x]);
	}
	
	// 부모 합치기 (집합 합치기)
	public static void unionParent(int a, int b) {
		int pa = findParent(a);
		int pb = findParent(b);
		
		if(pa<pb)
			parent[pb] = pa;
		else
			parent[pa] = pb;
	}
	
	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];
		
		// parent 배열에 부모노드는 자기 자신으로 초기화
		for(int i=0;i<=N;i++) {
			parent[i]=i;
		}
		
		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());
			
			// 우선 순위 큐에 넣기
			pq.offer(new Edge(from, to, cost));
		}
		
		// 결과 변수
		int result = 0;
		
		// 최소 신장 트리 중 가장 큰 간선
		int last = 0;
		
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			
			int from = edge.from;
			int to = edge.to;
			int cost = edge.cost;
			
			// 두 노드의 루트노드가 다르면 사이클 존재 X이므로, 최소 신장 트리에 추가
			if(findParent(from) != findParent(to)) {
				// 같은 집합으로 설정
				unionParent(from, to);
				
				// 결과 변수
				result += cost;
				
				// 작은 것부터 추가되니까 맨 마지막에 추가된 간선이 가장 길이가 큰 간선임.
				last = cost;
			}
		}
		
		// 추출한 최소 신장트리에서 가장 큰 간선을 빼면 마을이 2개 됨.
		System.out.println(result-last);
	}

}

 

 

3. 커리큘럼

- 위상 정렬 알고리즘을 이용해 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	// 과목 갯수
	public static int N;
	
	// 위상정렬
	public static int[] inde;
	
	// 시간
	public static int[] time;
	
	// 최소 시간(결과)
	public static int[] result;
		
	// 맵
	public static ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>();
	

	public static void topology() {
		Queue<Integer> q = new LinkedList<>();
		
		for(int i=1; i<=N; i++) {
			if(inde[i] == 0){
				q.offer(i);
			}
			result[i] = time[i];
		}
		
		
		while(!q.isEmpty()) {
			int now = q.poll();
			
			
			for(int i=0; i<map.get(now).size(); i++) {
				int d = map.get(now).get(i);
				
				result[d] = Math.max(result[d], result[now] + time[d]);
				//result[d] = result[now] + time[d]; 은 안될까? 결과는 같은데.. 
				inde[d] -= 1;
				if(inde[d] == 0) {
					q.offer(d);
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		N = Integer.parseInt(br.readLine());

		inde = new int[N+1];
		time = new int[N+1];
		result = new int[N+1];
		
		for(int i=0;i<=N;i++) {
			map.add(new ArrayList<Integer>());
		}
		
		for(int i=1;i<=N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			time[i]=Integer.parseInt(st.nextToken());
			
			while(true) {
				int temp = Integer.parseInt(st.nextToken());
				
				if(temp == -1)
					break;
				
				map.get(temp).add(i);
				
				inde[i] += 1;
			}
		}
		
		topology();
		
		for(int i=1; i<=N; i++) {
			System.out.println(result[i]);
		}
		
		
	}

}