STL pair에 관한 설명
vector<pair<int, int> > graph[3];
이렇게 선언하게 되면 (int형, int형) 을 가진 graph라는 벡터가 생겨난다.
또한 [3]으로 선언을 해주었으므로, 이중? 벡터라고 생각하면 편하다.
vector<pair<int, int> > graph[3];
g[0].push_back({3, 5});
g[0].push_back({4, 7});
g[0].push_back({5, 9});
g[1].push_back(make_pair(7, 7));
cout<<g[1][0].first<<" "<<g[1][0].second<<endl;이렇게 할 경우 아래와 같은 pair vetor가 생긴다.
그리고 결과는 7 과 7 이 출력된다.
오늘의 첫번째 문제
저번에 올렸던 경로 탐색과 똑같은 문젠데, 이번에는 인접리스트를 사용해서 푸는 것이다.
인접리스트란?
-> 그래프의 각 정점에 인접한 정점들을 '연결 리스트'로 표현한 것이다.
위 사진처럼 그래프의 각 정점들을 서로 꼬리에 꼬리를 무는 방식으로 표현한 것이다.
자 그러면 '왜?' 인접 행렬대신 인접 리스트를 쓰는 것이 편리한가?
인접 행렬로 경로 탐색을 하면, 처음 간선을 저장했던 2차원 배열 혹은 어떠한 배열들을 일일히 다 탐색을 해야한다. 예를들면 정점의 개수가 N이라고 치면, N x N 크기의 배열이 만들어지기 때문에 만약 정점의 개수가 천개만 되도, 백만번의 탐색을 해야 한다.
하지만 인접 리스트를 사용하게 되면, 꼬리에 꼬리는 무는 방식으로 저장을 하기 때문에, 인접 행렬마냥 일일히 다 확인해주면서, a에서 b로 가는 경로가 있는지 없는지를 확인할 필요가 없다. 그냥 처음 input을 받을 때, 벡터 배열에다 넣어주면 그 정점에 인덱스가 들어있으면, 그냥 말 그대로 그 인덱스로 가는 경로가 있는 것이다.
문제는 다음과 같다.
코드는 아래와 같다!
//66번
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector <int> map[30];
int ch[30]={0,}, cnt=0, N, M;
void DFS(int v){
if(v==N){
cnt++;
}
else{
for(int i=0; i<map[v].size(); i++){
if(ch[map[v][i]]==0){//인접 행렬이었다면 map의 값도 확인을 해줘야 함.
ch[map[v][i]] = 1;
DFS(map[v][i]);
ch[map[v][i]] = 0;
}
}
}
}
int main(){
int i, a, b;
cin>>N>>M;
for(i=0; i<M; i++){
cin>>a>>b;
map[a].push_back(b);
}
ch[1] = 1;
DFS(1);
cout<<cnt;
}오늘의 두번째 문제
최소비용에 관한 문제이다.
가중치 방향그래프가 주어지고, 1번 정점에서 N번 정점으로 가는 최소비용을 출력하는 프로그램을 작성해야한다.
이 글의 맨 처음에 보면 pair에 관하 STL 정리를 간단히 해두었는데, 바로 이 문제를 위해서이다.
아주 비슷한 메커니즘이지만 살짝 다른 면이 있다.
- 처음에 vector 선언을 해줄 때 pair vector로 선언을 해주어야 한다.
-> why? 가중치값도 저장을 해주어야하기 때문에 - DFS함수 부분에서 가중치의 값을 더했다 뺐다 해야한다.
-> 마치 ch[]배열의 값을 1과 0으로 번갈아가면서 바꿔주는 것을 통해 어떠한 정점을 내가 갔는지 안 갔는지 판별을 하는것처럼
코드는 다음과 같다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector< pair<int, int> > map[30];
int ch[30]={0,}, cnt=0, N, M, sum=0, minimum = 100000;
//강의를 보니까 DFS함수 인자 자체를 v갑과 가중치값으로 설정해주었는데
//그렇게 하는게 오히려 편할것 같긴하다..!
void DFS(int v){
if(v==N){
//cnt++;
if( sum <minimum){
minimum = sum;
}
}
else{
for(int i=0; i<map[v].size(); i++){
if(ch[map[v][i].first]==0){
ch[map[v][i].first] = 1;
sum = sum + map[v][i].second;
DFS(map[v][i].first);
sum = sum - map[v][i].second;
ch[map[v][i].first] = 0;
}
}
}
}
int main(){
int i, a, b, c;
cin>>N>>M;
for(i=0; i<M; i++){
cin>>a>>b>>c;
map[a].push_back({b, c});
}
ch[1] = 1;
DFS(1);
//cout<<cnt<<endl;
cout<<minimum;
}