9205번: 맥주 마시면서 걸어가기
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.
www.acmicpc.net
<풀이>
최단거리 문제집에 있어서 최단거리로 풀려고 했는데.. 접근 법이 떠오르지 않았다. 그래서 그냥 DFS로 풀었다.
주어진 조건을 보면 맥주 1병에 50미터를 갈 수 있다 햇으니 20병이 최대라면 항상 1000미터 까지 밖에 가지 못한다.
입력되는 좌표의 거리들을 비교하며 1000미터 이하로 갈 수 있다면 도달 가능하다는 것이기 때문에 이러한 좌표들을 인접리스트에 넣은 후 DFS 탐색을 해주었다.
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int t, n;
int ch[105];
vector<int> vec[105];
int dist(pair<int,int> p1, pair<int,int> p2){
return abs(p1.first-p2.first)+abs(p1.second - p2.second);
}
void DFS(int x){
for(int i=0; i<vec[x].size(); i++){
int nx = vec[x][i];
if(!ch[nx]){
ch[nx] = 1;
DFS(nx);
}
}
}
int main(void){
cin>>t;
while(t--){
for(int i=0; i<106; i++){
vec[i].clear();
}
memset(ch,0,sizeof(ch));
cin>>n;
vector<pair<int,int> > v;
for(int i=0; i<n+2; i++){
int a,b;
cin>>a>>b;
v.push_back(make_pair(a,b));
}
for(int i=0; i<n+2; i++){
for(int j=i+1; j<n+2; j++){
if(dist(v[i],v[j])<=1000){
vec[i].push_back(j);
vec[j].push_back(i);
}
}
}
DFS(0);
if(ch[n+1]){
cout<<"happy"<<"\n";
}else cout<<"sad"<<"\n";
}
}
14284번: 간선 이어가기 2
정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다.
www.acmicpc.net
<풀이>
오랜만에 다익스트라 문제 ! 양방향 그래프에 다 다른 가중치가 입력 되었고, 두 정점이 연결 되는 시점의 가중치 합의 최솟값 출력하라는 부분을 보고 바로 다익스트라 문제임을 떠올릴 수 있었다.
입력되는 정점 s로 탐색을 시작하며 지점이 t에 도달했을 때의 가중치 합을 출력해주면 된다.
너무 오랜만에 풀어서 그런지.. 가중치 더 하는 부분을 빼먹어서 ^^,,,, 로직을 다시 살펴보았다.... 다시 풀어보길 잘했네..
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct State{
int pos,dis;
State(int a, int b){
pos = a;
dis = b;
}
bool operator<(const State &nn) const{
return dis > nn.dis;
}
};
int n,m,s,t;
int main(void){
cin>>n>>m;
vector<pair<int,int> > vec[n+1];
vector<int> dist(n+1, 214700000);
int a,b,c;
for(int i=0; i<m; i++){
cin>>a>>b>>c;
vec[a].push_back(make_pair(b,c));
vec[b].push_back(make_pair(a,c));
}
cin>>s>>t;
priority_queue<State> que;
que.push(State(s,0));
dist[s] = 0;
while(!que.empty()){
int pos = que.top().pos;
int dis = que.top().dis;
que.pop();
if(dis>dist[pos]) continue;
if(pos == t){
cout<<dis<<"\n";
return 0;
}
for(int i=0; i<vec[pos].size(); i++){
int nxpos = vec[pos][i].first;
int nxdis = dis+vec[pos][i].second;
if(dist[nxpos]>nxdis){
dist[nxpos] = nxdis;
que.push(State(nxpos,nxdis));
}
}
}
}
'Algorithm > BOJ' 카테고리의 다른 글
| [ 백준 ] 47일차 - 16449번/2002번/18429번 (0) | 2021.10.13 |
|---|---|
| [ 백준 ] 46일차 - 1245번/2204번/2941번 (0) | 2021.10.12 |
| [ 백준 ] 44일차 - 12919번/16173번/16174번 (0) | 2021.10.07 |
| [ 백준 ] 43일차 - 2422번/5568번/18511번 (0) | 2021.10.06 |
| [ 백준 ] 42일차 - 11478번/17219번/6118번/11866번 (0) | 2021.10.05 |