백준 9205번 맥주 마시면서 걸어가기(C++)

문제

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를 이용해서 문제를 해결했다.

크게 두가지 조건이 가장 중요하다.

1. 일단 50미터당 한병을 마신다는 조건이 있고 최대로 갈 수 있는 거리는 X와 Y를 합쳐서 1000까지만 갈 수 있다.

2. 이동 중 편의점을 만나면 다시 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