문제출처 : https://www.acmicpc.net/problem/9205
1. 문제요약
- 집에서 편의점을 거져 목적지에 도달할 수 있는가?
- 1000m 이내의 다음 정점만 움직일 수 있음(맥주 20개, 개당 50m)
- 0 <= 편의점 개수, n <= 100
- -32768 <= 좌표 x, y <= 32767
2. 접근방법
- 경로가 있는지 찾는 문제 => 플로이드, 다익스트라
- 모든 정점을 다 방문해도 VE 이므로 시간 내에 들어올 것 같음 => bfs, dfs
※ 정점간 순서가 중요한 문제 : 위상정렬
정점간 사이클이 중요한 문제 : 오일러 서킷
3. 시간복잡도
- 플로이드 워셜 : N^3
- bfs, dfs : N^2
(한 정점당 다음 정점으로 가기 위해 살펴봐야 될 정점의 갯수 N * 정점의 갯수 N = N^2)
(한 정점에서 간선의 수가 100개라고 한다면 총 간선의 수 100 * 100, VE는 최대 100 * 100 * 100)
이 되겠지..? 여기선 간선의 수를 알 수 없으니
4. 회고
- 편의점간 1000m로
- bfs를 풀때 find를 왜넣었지 필요없네
소스코드 : 플로이드 워셜
#include<iostream>
#include<vector>
using namespace std;
int t, n;
vector<pair<int, int> > v;
vector<vector<int> > map;
int abs(int n){
return ((n < 0) ? -n : n);
}
bool dist(int x1, int y1, int x2, int y2){
return ((abs(x1 - x2) + abs(y1 - y2)) <= 1000 ? true : false);
}
int main(void){
cin >> t;
while (t--){
cin >> n;
v = vector<pair<int, int> >(n + 2, make_pair(0, 0));
map = vector<vector<int> >(n + 2, vector<int>(n + 2, 0));
for (int i = 0; i < n + 2; i++)
cin >> v[i].first >> v[i].second;
for (int i = 0; i < n + 2; i++)
for (int j = 0; j < n + 2; j++)
if (dist(v[i].first, v[i].second, v[j].first, v[j].second))
map[i][j] = map[j][i] = 1;
for (int k = 0; k < n + 2; k++)
for (int i = 0; i < n + 1; i++)
for (int j = 1; j < n + 2; j++)
if (map[i][k] && map[k][j])
map[i][j] = map[j][i] = 1;
cout << (map[0][n + 1] ? "happy" : "sad") << "\n";
}
return 0;
}
소스코드 : bfs
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int t, n;
vector<bool> check;
vector<pair<int, int> > v;
int abs(int x){
return ((x < 0) ? -x : x);
}
bool dist(int x1, int y1, int x2, int y2){
return ((abs(x1 - x2) + abs(y1 - y2)) <= 1000 ? true : false);
}
int main(void){
cin >> t;
while (t--){
cin >> n;
check = vector<bool>(n + 2, false);
v = vector<pair<int, int> >(n + 2, make_pair(0, 0));
for (int i = 0; i < n + 2; i++)
cin >> v[i].first >> v[i].second;
queue<int> q;
q.push(0);
check[0] = true;
bool find = false;
while (!q.empty()){
int now = q.front();
q.pop();
if (v[now].first == v[n + 1].first && v[now].second == v[n + 1].second){
find = true;
break;
}
for (int i = 1; i < n + 2; i++){
if (!check[i] && dist(v[now].first, v[now].second, v[i].first, v[i].second)){
q.push(i);
check[i] = true;
}
}
}
cout << (find ? "happy" : "sad") << "\n";
}
return 0;
}
소스코드 : dfs
#include<iostream>
#include<vector>
using namespace std;
int t, n;
vector<bool> check;
vector<pair<int, int> > v;
int abs(int x){
return (x < 0 ? -x : x);
}
bool dist(int x1, int y1, int x2, int y2){
return ((abs(x1 - x2) + abs(y1 - y2)) <= 1000 ? true : false);
}
void dfs(int now){
check[now] = true;
for (int i = 1; i < n + 2; i++)
if (!check[i] && dist(v[now].first, v[now].second, v[i].first, v[i].second))
dfs(i);
}
int main(void){
cin >> t;
while (t--){
cin >> n;
check = vector<bool>(n + 2, false);
v = vector<pair<int, int> >(n + 2, make_pair(0, 0));
for (int i = 0; i < n + 2; i++)
cin >> v[i].first >> v[i].second;
dfs(0);
cout << (check[n + 1] ? "happy" : "sad") << "\n";
}
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]