[Summer/winter Coding ~ (2018)] 배달

https://programmers.co.kr/learn/courses/30/lessons/12978?language=cpp

코딩테스트 연습 - 배달

 

(풀이)
인접리스트를 만들어 DFS를 이용하여 푼다.

(1) Input, 노드간 가중치가 최소인 거리만을 인접리스트로 만들어준다. _distance[][] 사용

(2) check[from][to]로 이전 노드에서 다음 노드까지 거리를 구해준다.

 이 거리를 구하는 이유는 재방문시 더 짧은 최단거리가 있으면 업데이트 해주기 위해서이다.

 

  만약, 위 예제2 에서 1->2->3 을 방문하면 이동거리는 3이되고, 3->5 까지 갈 수없다.

  하지만 1->3 ->5 는 이동거리는 4로  5 까지 방문이 가능하다. 

따라서 1->2->3 거리 3 보다 1->3 의 최단거리를 저장해준다. 

(3) check[next][0] = 방문(1) ; 을 저장해준다

 노드는 1~50 번까지이므로 0은 사용하지않음, 따로 visited 라는것을 만들지 않고
 그냥 0에 저장해서, [1][0] true 갯수만 출력해주면된다.

#include <iostream>
#include <vector>
#include<queue>
using namespace std;
int _distance[51][51];
int check[51][51];
vector<pair<int,int>> v[51];
int limit_time = 0;
void Input(vector<vector<int>> road);
void dfs(int idx, int sum);

int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;
    Input(road);
    limit_time = K;
    check[1][0] = true;
    dfs(1,0);
    
    for(int i=1;i<=50;++i)
        if(check[i][0]) answer+=1;    
 
    return answer;
}


void dfs(int node, int cur_time)
{
	for (int i = 0; i<v[node].size(); ++i)
	{
		int next = v[node][i].first;
		int n_time = cur_time + v[node][i].second;

        if(n_time >limit_time) continue;

        if(check[node][next] == 0 || check[node][next] >= n_time)
        {
		    check[next][0] = 1;
		    check[node][next] = n_time;
		    dfs(next, n_time);
        }

	}
}
void Input(vector<vector<int>> road)
{

    for(int i=0; i<road.size();++i)
    {
        int from = road[i][0];
        int to = road[i][1];
        int val = road[i][2];
        
        if(_distance[from][to]!=0 && _distance[from][to] < val) continue;
        
        _distance[from][to]=val;
        v[from].push_back(make_pair(to,val));
        v[to].push_back(make_pair(from,val));
        
        
    }
}