공부 기록

1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다.

문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다.

문제 조건

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

이 문제는 순서가 있다. 기본적으로 위상정렬을 이용 + 크기순으로 순회하면 될 것이라고 생각했다.

크기순으로 순회하기 위해서 PriorityQueue를 사용하도록 했다. 풀이는 아래와 같다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Integer> childs[] = new LinkedList[v + 1];
		LinkedList<Integer> parents[] = new LinkedList[v + 1];
		for (int i = 1; i <= v; i++) {
			childs[i] = new LinkedList<Integer>();
			parents[i] = new LinkedList<Integer>();
		}

		int[] parentNum = new int[v + 1];

		for (int i = 0; i < e; i++) {
			int parentNode = in.nextInt();
			int childNode = in.nextInt();

			childs[parentNode].add(childNode);
			parents[childNode].add(parentNode);
			parentNum[childNode]++;
		}

		traverseProblems(parentNum, childs, parents);
	}

	public static void traverseProblems(int[] parentNum, LinkedList<Integer> childs[], LinkedList<Integer> parents[]) {
		int problemNum = parentNum.length;
		boolean[] isVisited = new boolean[problemNum];

		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		for (int i = 1; i < problemNum; i++) {
			if (parentNum[i] == 0) {
				queue.add(i);
			}
		}

		while (!queue.isEmpty()) {
			int now = queue.poll();
			isVisited[now] = true;
			System.out.print(now + " ");

			for (int node : childs[now]) {
				parentNum[node]--;

				if (!isVisited[node] && parentNum[node] == 0) {
					queue.add(node);
				}
			}
		}
	}
}

문제 조건

1. 건물을 건설하는데 순서가 존재한다.

2. 건물 건설은 동시에 가능하다

이 문제는 전형적인 위상정렬 문제이다.

아래와 같이 건물을 건설하는 데에 필요한 정보는 아래 2가지 정보이며, 예제 1에 적용해 보자

- 기다려야 하는 시간 building

- 건물을 건설하기 위해 먼저 건설해야 하는 노드의 개수 parentNum

<time=0>



<time=10>

parentNum[i] = 0인 노드부터 건설하면 된다. 큐에 넣어서 순차적으로 처리해 보자

빌딩을 건설해 주고 나면 i를 부모 노드로 하는 자식 노드들의 parentNum을 하나씩 줄여준다.

<time=110>

빌딩은 동시에 건설이 가능하기 때문에,

같은 depth의 노드들의 building 중 최댓값을 time에 더해주도록 한다.

마지막으로 최종 목표 destination node가 나타나면 바로 건설 시간을 더해준 후 리턴해준다.

풀이 코드는 아래와 같다.

import java.util.*;

public class Main {
	public static int max = 0;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int test = in.nextInt();
		for (int t = 0; t < test; t++) {
			int v = in.nextInt();
			int e = in.nextInt();
			int building[] = new int[v + 1];

			for (int i = 1; i <= v; i++) {
				building[i] = in.nextInt();
			}

			LinkedList<Integer> childs[] = new LinkedList[v + 1];
			LinkedList<Integer> parents[] = new LinkedList[v + 1];
			for (int i = 1; i <= v; i++) {
				childs[i] = new LinkedList<Integer>();
				parents[i] = new LinkedList<Integer>();
			}

			int[] parentNum = new int[v + 1];

			for (int i = 0; i < e; i++) {
				int parentNode = in.nextInt();
				int childNode = in.nextInt();

				childs[parentNode].add(childNode);
				parents[childNode].add(parentNode);
				parentNum[childNode]++;
			}

			int destination = in.nextInt();

			System.out.println(calculateTime(destination, building, parentNum, childs, parents));
		}
	}

	public static int calculateTime(int destination, int[] building, int[] parentNum, LinkedList<Integer> childs[],
			LinkedList<Integer> parents[]) {
		boolean[] isVisited = new boolean[building.length];

		Queue<Integer> queue = new LinkedList<Integer>();
		for (int i = 1; i < building.length; i++) {
			if (parentNum[i] == 0) {
				if (i == destination) { // 바로 건설 가능한 경우
					return building[i];
				}

				queue.add(i);
			}
		}

		while (!queue.isEmpty()) {
			int now = queue.poll();
			isVisited[now] = true;

			for (int node : childs[now]) {
				parentNum[node]--;

				if (!isVisited[node] && parentNum[node] == 0) {
					queue.add(node);

					int max = 0;
					for (int parent : parents[node]) {
						max = Math.max(max, building[parent]);
					}
					building[node] += max;

					if (node == destination) {
						return building[destination];
					}
				}
			}
		}

		return building[destination];
	}
}

조금 어려웠던 점은 아래와 같은 반례를 생각하지 못했어서 맞왜틀을 고민했었다.

올바르게 시간을 구하기 위해서는 부모 노드들 또한 저장해야해야 했는데, 다른 스터디원들에 비해 실행 시간이 너무 오래 걸려서

한 번 생각해 봐야겠다...

문제 조건

1. 모든 방을 적어도 한 번은 방문한다.
2. 방을 방문하기 위한 순서가 있다.
   2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다.
   2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다.
   2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다.
   2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다. => 사이클이 없다

문제 조건을 읽으니 가장 먼저 위상 정렬을 이용해서 풀어야겠다는 생각이 들었다.

풀이 로직은 아래와 같다.

1. path를 이용하여 양방향 그래프를 생성한다.

2. 양방향 그래프를 bfs를 이용하여 방향 그래프로 바꾸어 준다.

3. 그래프에 order을 적용하여 위상 정렬 알고리즘을 돌린다.

class Solution {
	public static boolean solution(int n, int[][] path, int[][] order) {
		List<Integer>[] childs = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			childs[i] = new ArrayList<>();
		}

		for (int i = 0; i < path.length; i++) {
			childs[path[i][0]].add(path[i][1]);
			childs[path[i][1]].add(path[i][0]);
		}

		return isPossible(createGraph(childs), order);
	}

	public static List<Integer>[] createGraph(List<Integer>[] graph) {
		Queue<Integer> q = new LinkedList<>();
		List<Integer>[] directedGraph = new ArrayList[graph.length];
		for (int i = 0; i < directedGraph.length; i++)
			directedGraph[i] = new ArrayList<>();
		boolean[] v = new boolean[directedGraph.length];

		q.offer(0);
		v[0] = true;

		while (!q.isEmpty()) {
			int cur = q.poll();

			for (int i = 0; i < graph[cur].size(); i++) {
				int next = graph[cur].get(i);
				if (v[next])
					continue;

				directedGraph[cur].add(next);
				v[next] = true;
				q.offer(next);
			}
		}

		return directedGraph;
	}

	public static boolean isPossible(List<Integer>[] childs, int[][] order) {
		Queue<Integer> queue = new LinkedList<>();
		int[] parentNum = new int[childs.length];

		for (int i = 0; i < childs.length; i++) {
			for (Integer next : childs[i]) {
				parentNum[next]++;
			}
		}

		for (int i = 0; i < order.length; i++) {
			childs[order[i][0]].add(order[i][1]);
			parentNum[order[i][1]]++;
		}

		for (int i = 0; i < childs.length; i++) {
			if (parentNum[i] == 0) {
				queue.add(i);
			}
		}

		int cnt = 0;
		while (!queue.isEmpty()) {
			int cur = queue.poll();

			cnt++;

			for (int i = 0; i < childs[cur].size(); i++) {
				int next = childs[cur].get(i);
				parentNum[next]--;

				if (parentNum[next] == 0) {
					queue.add(next);
				}
			}
		}

		return cnt == childs.length ? true : false;
	}
}

위상 정렬 O(V + E)

• 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해 주기 위한 알고리즘
• 위상 정렬은 사이클이 없는 그래프에서만 사용 가능하다.
• 스택 또는 큐를 이용해서 구현할 수 있다.

위상정렬의 구현 방법

1. 진입차수(부모 노드의 수)가 0인 정점을 큐에 넣는다
2. 큐에서 노드를 꺼내고, 이 노드에 연결된 모든 간선을 끊는다.
3. 간선 제거 이후 진입차수가 0이 된 정점을 넣는다.
4. 큐가 빌 때까지 2~3 반복

import java.util.*;
class Solution {
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int test = 10;
        for (int t = 1; t <= test; t++) {
            int v = in.nextInt(); // 정점
            int e = in.nextInt(); // 간선
 
            LinkedList<Integer> childs[] = new LinkedList[v + 1];
            for (int i = 0; i <= v; i++) {
                childs[i] = new LinkedList<Integer>();
            }
 
            int[] parentNum = new int[v + 1];
            boolean[] isVisited = new boolean[v + 1];
            for (int i = 0; i < e; i++) {
                int parentNode = in.nextInt();
                int childNode = in.nextInt();
 
                childs[parentNode].add(childNode);
                parentNum[childNode]++;
            }
 
            Queue<Integer> queue = new LinkedList<Integer>();
            for (int i = 1; i <= v; i++) {
                if (parentNum[i] == 0) {
                    queue.add(i);
                }
            }
 
            StringBuilder sb = new StringBuilder("#" + t + " ");
            while (!queue.isEmpty()) {
                int now = queue.poll();
                isVisited[now] = true;
                sb = sb.append(now + " ");
 
                LinkedList<Integer> links = childs[now];
                for (int node : links) {
                    parentNum[node]--;
                    if (!isVisited[node] && parentNum[node] == 0) {
                        queue.add(node);
                    }
                }
                links.clear();
            }
 
            System.out.println(sb);
        }
    }
}