[프로그래머스] 배달 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

풀이 방법

이것은 DFS인가 BFS인가

스택을 사용한 BFS 코드?가 탄생했다.

 

쨋든.

순환 함수로 탐색을 구현하면 깔끔하게 문제가 풀리겠지만

스택을 고집하여 풀었다.

 

방문 여부 bool 배열을 사용하자니

위와 같은 한 마을로 가는 경로가 2개인 경우가 있어 섣불리 visit로 해버리면

나중에 더 저렴한 비용으로 도착했을때

마을을 통과가 가능할 수 있는데 

단지 방문한적이 있다는 이유로 방문을 안해버리는 참사가 일어난다.

 

그래서

 

핵심은 Map을 통해 A->B를 가는 누적 비용을 저장해 놓았다가

경로와 비용을 통해 중복된 방문은 회피하여 탐색을 진행한다는 것이다.

 

이때 visit 배열을 사용하지 않으므로

탐색시 다음 마을이 1번 마을인 경우를 주의해서 코드를 작성해야한다.

( if(next!=1) )

 

전체 코드

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <map>
using namespace std;

int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;

    map<pair<int,pair<int,int>>, bool> m; // a에서 b로 가는데 드는 비용 c 방문 여부 ex:{(A,B,10), true}
    bool able[51]; // i 마을 방문 가능 여부
    fill(able, able+51, false);
    
    vector<pair<int, int>> v[51]; // a에서 b로 가는 비용 (a, b, cost)
    for(int i=0; i<road.size(); i++) {
        // 양방향
        v[road[i][0]].push_back(make_pair(road[i][1], road[i][2]));
        v[road[i][1]].push_back(make_pair(road[i][0], road[i][2]));
    }
    
    stack<pair<int,int>> s; // (현재 위치, 현재 총 비용)
    s.push(make_pair(1, 0)); // 1번 마을부터 시작. 현재 0 비용
    able[1]=true;
    
    while(!s.empty()) {
        int cur = s.top().first; // 현재 위치
        int cost = s.top().second; // 현재 비용
        s.pop();
        
        for(int i=0; i<v[cur].size(); i++) {
            int next = v[cur][i].first; // 다음 마을
            int nextCost = v[cur][i].second; // 다음 마을 도로의 비용
            if(m.find(make_pair(cur,make_pair(next, cost+nextCost)))==m.end() // a->b 비용 c를 방문한 적이 없다면
               && cost+nextCost<=K // 현재 비용과 다음 마을까지 이동 비용 합이 K보다 작거나 같다면
               && next!=1) { // 다음 마을은 1번 마을이 아니여야함
                s.push(make_pair(next, cost+nextCost)); // 다음 마을 번호와 총 비용 push
                m.insert({make_pair(cur, make_pair(next, cost+nextCost)), true}); // a->b의 비용 저장
                able[next]=true; // cur의 다음 마을인 next 배달이 가능하므로 able에 true로.
            }
        }
    }
    
    for(int i=1; i<=N; i++) { // 방문 가능한 마을 카운트
        if(able[i])
            answer++;
    }

    return answer;
}