[임시글] 경작 21일차 최단경로 알고리즘

#230219 일

1. 백준 1753번 최단경로

---

<문제>
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

<입력>
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

<출력>
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

---

2. 백준 10282번 해킹

---

<문제>
최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.
최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

<입력>
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.
• 각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

<출력>
각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

*임시저장..

---

#include <iostream>
#include <vector>
using namespace std;
int casenum;  //테스트 케이스의 개수
int cptnum;   //컴퓨터 개수
int connum;   //의존성 개수
int hcpt;     //해킹당한 컴퓨터 번호


void gfunction(){
    bool included[10001] = {false,};   //included false로 초기화
    vector<int>adj[10001];             //인접 리스트
    int timearray[10001][10001]= {0,};      //시간 리스트 0으로 초기화(3차원 배열 만들 줄 몰라서..ㅋ)

    cin>>cptnum>>connum>>hcpt;         //입력 받음 
    for(int i=0;i<connum;i++){ 
        int s, e, t; 
        cin>>s>>e>>t;                  //출발정점, 끝정점, 시간
        if(timearray[s][e]==0){        //지금까지 들어온 입력이 없으면or 0이면
            adj[s].push_back(e);       //
            timearray[s][e] = t; 
        }
        else if(t < timearray[s][e]){    //이전에 입력된 시간보다 작은 입력이 들어오면
            adj[s].push_back(e);       
            timearray[s][e] = t; 
        }
    }

    vector <int> distance;
    vector <int> previous;
    for(int i=1;i<=cptnum;i++){
        distance[cptnum] = 1001;     //distance는 inf로 초기화
        previous[cptnum] = -1;       //이전 정점은 -1로 초기화
    }
    previous[hcpt] = 0;              //시작 컴퓨터의 이전 정점은 0
    distance[hcpt] = 0;              //시작 정점의 거리는 0으로 

    int tmp;
    int minvalue;

    for(int i=1;i<=cptnum;i++){
        tmp=-1;
        minvalue = 1001;
        for(int j=1;j<=cptnum;j++){
            if(!included[j] && distance[j] < minvalue){
                minvalue = distance[j];
                tmp = j;
            }
        }
        included[tmp] = true; 

        for(int k=0;k<adj[tmp].size();k++){
            int idx = adj[tmp][k];
            idx++;
            if(!included[idx] && (distance[tmp] + timearray[tmp][k]) < distance[idx]){
                distance[idx] = distance[tmp] + timearray[tmp][k];
                previous[idx] = tmp;
            }
        }
    }

    int maxtime=0;
    int sum=0;
    for(int i=0;i<cptnum;i++){
        if(distance[i] != 1001){
            sum++;
            if(maxtime < distance[i]){
                maxtime = distance[i];
            }
        }
    }
 
    cout<<sum<<' '<<maxtime ;

    cout<<0;
}


int main(){
    cin>>casenum;

    for(int i=0;i<casenum;i++){
        gfunction();
        cout<<'\n';
    }
    return 0;
}