C - 1005 ACM Craft

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

 

https://github.com/shirohebiui/BAEKJOON/blob/2774a05a6501034cdb02ed98895bb8370a68a721/%23DP/G/1005(G3)BFS/1005%20solve.c

 

여러 정점과 이를 연결하는 간선이 주어진다.

각 정점에는 작업량에 해당하는 값이 있고

각 간선은 단방향 간선이다.

 

목표는 목적지 노드까지 도착하는 모든 정점을 탐색하고 목적지까지 걸리는 최장시간을 탐색하는것이다.

최장시간을 탐색하지만 출발이 하나가아닌 다수에서 동시에 가능하므로 DFS가 아닌 BFS적 논리로 접근해야한다.

 

아래 기본적인 아이디어(작은문제)를 그림으로 그려보고

작은 문제를 이어 붙여 큰문제를 만들어 예외가 존재하는 경우를 생각해 보았다.

 

큰 문제로 보아도 예외가 없다고 판단한 후 매번 풀어야하는 문제에 대한 점화식을 자연어로 써 보았다.

 

이제 이 아이디어를 구현해 볼 것이다.

처음 입력받을 시 graph에서 간선의 연결을 역순으로 보고 저장한다. 왜냐하면 탐색은 목적지부터 연결된 노드를 탐색할 생각이니

A->B->C순서로 연결되는게 아닌 C->B->A 순으로 연결되어야 연결된 노드를 확인할 수 있기때문이다.

 

입력을 받는 방식

#define MAX 1001
int dp[MAX]; //consider (workload)
char graph[MAX][MAX];

int vertex; //정점 갯수
int edge; //간선 갯수

void input_work() {
    for(int i=1; i<=vertex; i++)
        scanf(" %d", &dp[i]);
}

void input_graph() {
    int i, j;
    for(int t=1; t<=edge; t++) {
        scanf("%d %d", &i, &j);
        graph[j][i] = 1; //뒤에서부터 탐색할거니까 반대로 연결
    }
}

 

이제 입력된 값을 토대로 목적지까지의 최장시간을 알아볼 것이다.

dp[i] = max(node i에 연결된 "모든" node j = dp[j])

이 식을 토대로 구현해보았다.

int dpbfs(int node) {
    int max = 0;
    for(int i=1; i<=vertex; i++) { //노드와 연결된 다른노드들 탐색
        if(graph[node][i]) {	//안 푼 문제 : 풀러 들어감
            graph[node][i] = 0; //푼 문제로 체크 : 간선 연결 제거
            max = max > dpbfs(i) ? max : dpbfs(i); //비교 후 큰값을 저장
        }
    }
    dp[node] += max;
    return dp[node]; //해당 노드에서 최장시간 리턴
}

 

이제 이 함수를 토대로 목적지를 구해보면 잘 구해진다.

dp는 1차원배열로 정점이 주어지면 그 정점의 갯수까지만 탐색해서 매번 새로 초기화가 자연스럽게 되지만

graph는 2차원 배열로 이전 간선이 남아있을 수 있다.

따라서 매 루프마다 graph의 초기화는 직접 해줘야한다.

int main() {
    int TestCase; scanf("%d", &TestCase); //테스트 횟수
    while(TestCase--) {
        memset(graph, 0, sizeof(graph)); //그래프초기화
        scanf("%d %d", &vertex, &edge); //정점갯수
        input_work();
        input_graph();
        int dest; scanf(" %d", &dest); //목표노드
        printf("%d\n", dpbfs(dest));
    }
    return 0;
}

 

예제 입력 1, 2