Hyun's_Devlog

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

위상정렬로 접근한 문제다.

풀이

해당 문제의 컴퓨터는 자료를 전송할 다음 등급의 컴퓨터가 여러 대라면 동시에 자료를 전송하는 것으로 계산하면 된다. 즉 위상정렬을 통해 다음 등급의 컴퓨터를 탐색할 때, 간선의 비용이 최대 값인 경우만 찾아내면 된다.

입력되는 등급을 통해 위상정렬 순서를 구해 탐색을 수행한다. (다음 등급의 컴퓨터에게 자료를 전달하는 시간 + 다음 컴퓨터의 구동시간)의 최댓값을 저장할 ans 배열을 생성. 매 탐색마다 해당 배열을 최댓값으로 갱신하고 탐색이 종료된 후 ans 배열의 최댓값을 출력하면 정답이다.

예제를 기준으로 다음과 같이 수행된다.

가장 먼저 가장 낮은 등급의 컴퓨터인 1번과 7번 컴퓨터가 동작한다.

각자의 (동작시간 + 전송시간)의 값 중 가장 큰 값이 다음 등급인 6번 컴퓨터에게 전달되며,

해당 컴퓨터는 자신의 구동시간을 더해 ans배열에 갱신한다.

이후 탐색 큐에 6과 ans [6]의 값 36을 담아 다음 탐색을 수행한다.

2등급 컴퓨터인 6번 노드는 다음 등급의 컴퓨터인 2번과 3번 컴퓨터에 자료를 전송.

6번 컴퓨터의 대기시간 + 동작시간의 값 + 전송시간의 값이 전달된다.

이제 해당 값에 2번과 3번 컴퓨터의 구동시간을 더해 ans배열을 갱신한다.

각 노드로 진입하는 대기시간 + 구동시간 + 전송시간의 값 중 가장 큰 값을 입력받아 ans배열을 갱신해 나가면 된다.

구동시간에는 음수가 입력되지 않으므로 마지막 컴퓨터의 대기시간 + 구동시간 + 동작시간을 더해 출력하면 된다.

정답 코드

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

위상정렬 문제다.

풀이

사이클이 생기는 노드, 그리고 해당 노드로 진입하는 노드를 제외한 나머지 노드의 수를 출력하는 문제다. 

주어지는 간선의 방향을 반대로 저장하고 위상정렬을 통해 탐색한다면, 정답을 구할 수 있다. 이유는 위상정렬의 필수조건인 indegree가 0인 노드를 큐에 담아 탐색하는 부분에서 찾을 수 있다. 사이클이 발생한다는 것은 곧 indegree가 0이 되지 않는다는 이야기이기에 역방향으로 탐색하게 되면 사이클은 큐에 담기지 않게 된다.

예제의 경우를 그래프로 그려보면 좌측과 같다. 위상정렬을 통해 탐색을 시작하면 1부터 시작하기에 처음부터 사이클이 일어날지 알 수 없다. 반면 우측의 경우처럼 역방향으로 그래프를 그리면 4와 6만 큐에 담긴 채 사이클이 일어나는 3번 노드는 큐에 담기지 않게 되고 그대로 탐색이 종료된다. 따라서 정답은 4, 6번 학생인 두 명의 부원이라는 정답을 출력할 수 있다.

정답 코드

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

위상정렬로 접근한 문제다.

풀이

입력받은 정보를 기반으로 매 순간 비용의 최댓값으로 갱신하여 위상정렬 순서로 탐색한다. 이후 비용의 최댓값을 출력하면 된다.

각 노드의 진입차수와 노드의 비용 그리고 최종으로 출력할 ans 배열을 생성한다.

가장 먼저 진입차수가 0인 노드를 큐에 넣고 탐색을 시작. 이때 노드에 해당하는 ans는 해당 노드의 cost로 결정된다.

이후 탐색가능한 노드의 ans 값은 ans [현재노드] + cost [탐색가능 노드]와 ans [탐색가능 노드] 중 더 큰 값으로 갱신된다.

다음 탐색을 통해 ans [C]가 8+2의 값으로 갱신되는 모습이다.

다음 탐색으로 ans [E]의 값이 0에서 ans [D] + cost [E]의 값으로 경신.

C노드의 탐색으로 ans [E] 값이 기존보다 더 큰 값인 ans [C] + cost [E]의 값 14로 갱신된다.

이후 E의 진입차수가 0이므로 큐에 삽입되고 탐색이 이루어진다.

ans [F]의 값이 16으로 최종 경신된다.

마지막으로 F노드 방문. 더 이상 탐색가능한 노드가 없으므로 탐색 종료.

ans의 값 중 가장 큰 값을 출력하면 된다.

정답 코드

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

위상정렬 문제다.

풀이

처음 문제를 읽었을 때는 기본부품부터 완성품까지 위상정렬로 탐색하여 부품의 개수를 세는 방법으로 접근하였는데, 그렇게 되면 기본부품을 파악하기 힘들어진다.

따라서 완성품에서 기본 부품 순서로 위상정렬을 통해 접근하여 탐색하였다. 마지막 노드라면 해당 부품의 cost를 출력하는 방법으로 접근했다. 

부품의 비용을 담을 크기 N의 cost배열과, 간선정보를 (다음노드 번호, 비용) 형태로 담을 크기 N의 튜플배열을 생성. 진입차수가 0인 N번 노드를 시작으로 현재 cost X 다음 cost를 배열에 갱신하여 참색을 수행하였다. 입력 예제의 시나리오를 그림으로 표현하면 다음과 같다.

각 노드의 진입 차수, 실시간 비용, 그리고 마지막으로 출력할 정답 배열을 생성한다.

가장 첫 번째로 진입 차수가 0인 7번 노드 방문, 4번, 6번, 5번 부품의 비용을 갱신한다.

(현재 비용 * 간선 비용)을 통해 계산이 가능하다.

다음으로 진입 차수가 0인 6번 노드 방문. 탐색을 시작한다. 인접 노드의 비용을 갱신.

3번 노드를 방문. 이때 3번 노드의 경우 더 이상 탐색 가능한 인접 노드가 없다.

3번 부품을 생산하기 위한 다른 부품은 필요 없다는 뜻이므로 ans 배열에 해당 비용을 반영한다.

다음으로 진입 차수가 0인 4번 노드 방문. 마찬가지로 더 이상 탐색 가능한 인접 노드가 없으므로 현재 비용을 ans 배열에 반영한다.

다음으로 5번 노드 방문 인접 노드인 1번 노드와 2번 노드에 (현재 부품 비용 * 간선 비용)을 계산하여 cost배열에 값을 반영한다.

1번 노드 방문. 더 이상 탐색 가능한 노드가 없다. ans 배열에 현재 비용을 반영한다.

마지막으로 2번 노드 방문. 더 이상 탐색 불가능 하므로 ans 배열에 현재 cost를 반영한다.

완성된 ans 배열을 통해 0이 아닌 값들을 출력하면 정답이다.

정답 코드

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

위상정렬과 동적계획법으로 접근가능한 문제다.

풀이법

처음에는 단순히 위상정렬을 통해 큐에 접근할 때마다 가장 오래 걸린 작업시간들을 더하면 될 것이라 생각했다. 하지만 해당방법은 틀린 방법이 다.

후속이 없는 작업의 경우, 다음 탐색에  영향을 끼치지 않아야 하는데, 처음생각한 방법은 이러한 부분을 제외시키지 못했다. 따라서 해당 작업을 완료하는데 걸리는 총시간을 담은 dp 배열을 생성한 뒤, 동적계획법으로 접근해야 한다. next는 다음 작업, curr는 현재작업을 의미할 때, 점화식은 다음과 같다. 여기서 time배열은 순수 작업시간을 의미한다.

dp[next] = max(dp[next], dp[curr]+time[next])

위상정렬을 통한 그래프탐색 이후, dp배열의 최댓값을 출력하면 된다.

정답 코드

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

위상정렬 문제다.

풀이

문제에서 요구하는 것은 선수과목의 순서가 아니라 각 과목을 듣기 위한 최소 학기수.

즉 위상정렬을 사용하여 큐에 몇번 접근하는지를 파악하면 된다. 

입력되는 값을 통해 각 노드의 진입차수를 저장. 진입차수가 0인 노드를 큐에 담아놓고 그래프탐색을 수행하면 된다.

그래프탐색을 통해 다른 노드로 진입시, 해당노드의 진입차수를 하나씩 차감. 0이 된다면 다음 탐색큐에 추가하면 된다.

문제의 정답을 계산하기 위해 반복문을 구분하여 탐색해야 한다. 해당 부분은 코드르 보는 게 이해하기 쉬울 것이다.

정답 코드