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

9205번: 맥주 마시면서 걸어가기

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

 

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다. 

 

 

풀이과정

문제에서는 맥주가 20병이 있고 1병당 50m를 갈 수 있다고 설명을 하고있지만, 상근이가 편의점에 가면 모든 맥주의 개수가 다 채워지므로

20 * 50 = 1000m로 상근이의 위치를 기준으로 1000m내에 갈 수 있는 곳이 있다면 상근이는 이동을 할 수 있다.

위와 같은 형식으로 상근이가 1000m내에 락 페스티벌 갈 수 있는 위치가 가능한가 라는게 문제의 조건이었다.

 

이 문제도 마찬가지로 모든 경우를 다 탐색을 해보고 도착할 수 있다면 "happy" 출력

도착할 수 없다면 "sad" 출력

으로 전체적인 로직을 구상하였다.

 

1. 상근이의 현재 위치기준으로 1000m 내에 락페스티벌이 위치해있다면 "happy" 출력 후 종료
2. 1000m 내에 이동할 수 있는 편의점이 있다면 queue에 저장 ( 이미 방문한 편의점이라면 건너뛰기 )
3. queue.front를 뽑아서 상근이의 위치를 편의점의 위치로 갱신

위에 적은 로직이 무한 반복이었다.

1000m내로 이동할 수 있는지 없는지 확인하는 방법은

pos = std::abs(A.Y - B.Y) + std::abs(A.X - B.Y)

temp = std::abs(C.Y - D.Y) + std::abs(C.X - D.Y)

위와 같은 형식으로 pos와 temp에 차이가 절대값 1000안에 있다면 이동을 할 수 있었다.

code

#include <iostream>
#include <vector>
#include <queue>

int beer = 1000;
std::vector <std::pair<int, int> > shop;
bool check[101];

void	bfs(std::pair<int, int> home, std::pair<int, int> rage)
{
	int temp;
	bool output = false;
	std::queue <std::pair<int, int> > que;
	std::pair <int, int> pos;

	que.push(std::make_pair(home.first, home.second));
	while (!que.empty())
	{
		pos = que.front();
		que.pop();
		temp = std::abs(pos.first - rage.first);
		temp += std::abs(pos.second - rage.second);
		if (temp <= beer) {
			output = true;
			break;
		}
		for (int i = 0; i < shop.size(); i++) {
			temp = std::abs(pos.first - shop[i].first);
			temp += std::abs(pos.second - shop[i].second);
			if (temp <= beer && !check[i]) {
				que.push(std::make_pair(shop[i].first, shop[i].second));
				check[i] = true;
			}
		}
	}
	if (output == true) std::cout << "happy" << "\n";
	else std::cout << "sad" << "\n";
}

int		main(void)
{
	int t, n;
	std::pair <int, int> home, rage, temp;

	std::cin >> t;
	for (int i = 0; i < t; i++) {
		std::cin >> n;
		std::cin >> home.first >> home.second;
		for (int j = 0; j < n; j++) {
			std::cin >> temp.first >> temp.second;
			shop.push_back(temp);
		}
		std::cin >> rage.first >> rage.second;
		bfs(home, rage);
		std::fill_n(check, 100, false);
		shop.clear();
	}
}

 

후기

반례를 고려하지못하고 bfs가 아닌 방식으로 문제를 접근했어서 오랜시간이 걸렸던 거 같다.

문제를 접근할때 더 깊게 생각을 해보고 확실하게 접근을 해봐야할 거 같다.