문제
9205번: 맥주 마시면서 걸어가기
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.
https://www.acmicpc.net/problem/9205
정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
int t_case;
int n;//편의점 갯수
int home_x, home_y;
int dest_x,dest_y;
bool vis[101];
//-32768 ~ 32767 이므로 65535가 32767로 0이 -32768로
//20개씩 50미터
//즉 1개당 50미터이므로
//최대 이동거리 1000미터
using namespace std;
//정답을 만들 수 있으면 true
//없다면 false
bool make_ret(vector<pair<int,int>> &store,int now_x,int now_y){
int store_s = store.size();
int f_dist_y = abs(now_y - dest_y);
int f_dist_x = abs(now_x - dest_x);
int f_dist = f_dist_y + f_dist_x; // 현재 위치에서 도착지점까지 거리
if (f_dist <= 1000)
return (true);
for(int i=0;i<store_s;i++){
if (vis[i])
continue;
int dist_x = abs(now_x - store[i].first);
int dist_y = abs(now_y - store[i].second);
int store_dist = dist_x + dist_y;
if (store_dist > 1000)
continue;
vis[i] =true;
if (make_ret(store,store[i].first,store[i].second))
return true;
// vis[i] = false;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> t_case;
for(int i=0;i< t_case;i++){
vector<pair<int,int>>store;
cin >> n;
cin >> home_x >> home_y;
int x,y;
for(int j=0;j<n;j++){
cin >> x >> y;
store.push_back({x,y});
}
cin >> dest_x >> dest_y;
if (make_ret(store,home_x,home_y))
cout << "happy\n";
else
cout << "sad\n";
memset(vis,0,sizeof(vis));
}
}문제 풀이의 흐름
이 문제는 풀 수 있는 방법이 크게 작게보면 1가지 크게보면 2가지가 있는 문제인 것 같다.
로직은 같다. 다만 나는 DFS를 이용해서 문제를 해결했다.
크게 두가지 조건이 가장 중요하다.
- 일단 50미터당 한병을 마신다는 조건이 있고 최대로 갈 수 있는 거리는 X와 Y를 합쳐서 1000까지만 갈 수 있다.
- 이동 중 편의점을 만나면 다시 1000만큼 이동할 수 있다.
이 두가지 조건을 이용해서 문제를 보다보면 한가지 사실을 발견할 수 있다.
편의점을 한번 방문 한 곳은 다시 돌아오는 일은 없다는 것이다.
이게 이해가 안 간다면 한번 깊이 DFS를 해보면서 다시 방문할일이 있을까를 고민해보길 바란다.
주의 할 점
vis를 false로 바꾸지 않아도 된다는 사실을 유념하자.
사실 이것을 깨닫지 못해서 vis를 다시 false로 바꾸는 실수를 했어서 계속해서 시간초과가 나서 모의 코테에서 실패했었다.
왜 false로 안 바꿔도 되냐? 이미 한번 방문했던 곳에서 갈 수 있는 모든 편의점을 결국 dfs로 방문을 하게 되는데 다음으로 방문한 편의점은 이전에 방문했던 편의점을 방문하면 이전에 정답을 찾아보던 깊이우선 탐색을 했던 곳을 또 한번 더 가는 것이기 때문에 내부에서 엄청나게 많은 시간이 걸릴 가능성이 등장한다.
반성 및 고찰
시간 초과 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
int t_case;
int n;//편의점 갯수
int home_x, home_y;
int dest_x,dest_y;
bool vis[101];
//-32768 ~ 32767 이므로 65535가 32767로 0이 -32768로
//20개씩 50미터
//즉 1개당 50미터이므로
//최대 이동거리 1000미터
using namespace std;
//정답을 만들 수 있으면 true
//없다면 false
bool make_ret(vector<pair<int,int>> &store,int now_x,int now_y){
int store_s = store.size();
int f_dist_y = abs(now_y - dest_y);
int f_dist_x = abs(now_x - dest_x);
int f_dist = f_dist_y + f_dist_x; // 현재 위치에서 도착지점까지 거리
if (f_dist <= 1000)
return (true);
for(int i=0;i<store_s;i++){
if (vis[i])
continue;
int dist_x = abs(now_x - store[i].first);
int dist_y = abs(now_y - store[i].second);
int store_dist = dist_x + dist_y;
if (store_dist > 1000)
continue;
vis[i] =true;
if (make_ret(store,store[i].first,store[i].second))
return true;
vis[i] = false;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> t_case;
for(int i=0;i< t_case;i++){
vector<pair<int,int>>store;
cin >> n;
cin >> home_x >> home_y;
int x,y;
for(int j=0;j<n;j++){
cin >> x >> y;
store.push_back({x,y});
}
cin >> dest_x >> dest_y;
if (make_ret(store,home_x,home_y))
cout << "happy\n";
else
cout << "sad\n";
memset(vis,0,sizeof(vis));
}
}틀린 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
int t_case;
int n;//편의점 갯수
int home_x, home_y;
int dest_x,dest_y;
bool vis[101];
//-32768 ~ 32767 이므로 65535가 32767로 0이 -32768로
//20개씩 50미터
//즉 1개당 50미터이므로
//최대 이동거리 1000미터
using namespace std;
//정답을 만들 수 있으면 true
//없다면 false
bool make_ret(vector<pair<int,int>> &store,int now_x,int now_y){
int store_s = store.size();
int f_dist_y = abs(now_y - dest_y);
int f_dist_x = abs(now_x - dest_x);
int f_dist = f_dist_y + f_dist_x; // 현재 위치에서 도착지점까지 거리
if (f_dist <= 1000)
return (true);
for(int i=0;i<store_s;i++){
if (vis[i])
continue;
int dist_x = abs(now_x - store[i].first);
int dist_y = abs(now_y - store[i].second);
int store_dist = dist_x + dist_y;
if (store_dist > 1000)
continue;
int s_dist_y = abs(store[i].first - dest_x);
int s_dist_x = abs(store[i].second - dest_y);
int s_dist = s_dist_x + s_dist_y; //새로 가는 가게 위치에서 도착 지점까지 거리
if (s_dist > f_dist)
continue;
vis[i] =true;
if (make_ret(store,store[i].first,store[i].second))
return true;
vis[i] = false;
}
return false;
}
int main(){
cin >> t_case;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i=0;i< t_case;i++){
vector<pair<int,int>>store;
cin >> n;
cin >> home_x >> home_y;
int x,y;
for(int j=0;j<n;j++){
cin >> x >> y;
store.push_back({x,y});
}
cin >> dest_x >> dest_y;
if (make_ret(store,home_x,home_y))
cout << "happy\n";
else
cout << "sad\n";
memset(vis,0,sizeof(vis));
}
}조금 당황해서 자꾸 삽질을 했는데 테스트 할 때 냈던 코드랑 한줄만 바꾸니까 통과하니까 살짝 허무하기도 하다. 앞으로 조금 더 DFS에 대한 이해를 높일 수 있는 문제였다.
Uploaded by N2T