문제 조건

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];
	}
}

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

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

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

'알고리즘 공부 > boj' 카테고리의 다른 글

boj 1939: 중량제한  (0) 2021.01.20
boj 17143: 낚시왕  (0) 2021.01.20
boj 1949: 우수 마을  (0) 2021.01.19
boj 1981: 배열에서 이동  (0) 2021.01.17
boj 3745: 오름세  (0) 2021.01.15

+ Recent posts