쌓고 쌓다
[프로그래머스] 배달 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;
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 숫자 카드 나누기 C++ 풀이 및 해설 (0) | 2023.09.19 |
---|---|
[프로그래머스] 마법의 엘리베이터 C++ 풀이 및 해설 (0) | 2023.09.13 |
[프로그래머스] 호텔 대실 C++ 풀이 및 해설 (0) | 2023.08.30 |
[프로그래머스] 줄 서는 방법 C++ 풀이 및 해설 (0) | 2023.08.27 |
[프로그래머스] 전력망을 둘로 나누기 C++ 풀이 및 해설 (0) | 2023.08.21 |
Comments